Pyöreä linkitetty luettelo: edut ja haitat

Mikä on pyöreä linkitetty luettelo?

Ympyrälinkitetty lista on solmujen sarja, joka on järjestetty siten, että jokainen solmu voidaan uudelleenjärjestää.tracitseensä. Jokainen ”solmu” on itseensä viittaava elementti, jolla on osoittimet yhteen tai kahteen solmuun sen välittömässä läheisyydessä.

Alla on esitys pyöreästä linkitetystä luettelosta, jossa on 3 solmua.

Tässä näet, että jokainen solmu on uudelleentracitselleen mahdollinen. Yllä oleva esimerkki on ympyrämäinen, kerran linkitetty lista.

Huomautus: Yksinkertaisin ympyrälinkitetty lista on yksittäinen solmu, jonka seuraava osoitin tracpalautuu takaisin itseensä, kuten alla on esitetty.

Perus Operaympyrälinkitettyjen listojen funktiot

Ympyrämäisen linkitetyn listan kolme perusoperaatiota ovat:

1. lisäys
2. Poisto ja
3. traversal

• Lisäys on prosessi, jossa solmu asetetaan tiettyyn kohtaan pyöreässä linkitetyssä luettelossa.
• Poistaminen on prosessi, jossa olemassa oleva solmu poistetaan linkitetystä luettelosta. Solmu voidaan tunnistaa sen arvon esiintymisen tai sijainnin perusteella.
• Ympyrämäisen linkitetyn listan läpikäyminen on prosessi, jossa näytetään koko linkitetyn listan sisältö jatractakaisin lähdesolmuun.

Seuraavassa osiossa selitetään, miten lisäys toimii ja mitkä kaksi lisäystyyppiä ovat mahdollisia ympyrämäisessä, yksittäin linkitettyssä listassa.

lisäys OperaTUKSEN

Ensin luodaan yksi solmu, jonka seuraava osoitin osoittaa takaisin itseensä, kuten alla on esitetty. Ilman tätä siemensolmua ensimmäisestä lisäyksestä tulee listan ensimmäinen solmu.

Seuraavaksi on kaksi mahdollisuutta:

• Lisäys ympyrälinkitetyn listan nykyiseen kohtaan. Tämä vastaa lisäystä joko tavallisen kerran linkitetyn listan alkuun tai loppuun – ympyrälinkitetyssä listassa alku ja loppu ovat samassa pisteessä.
• Lisäys indeksoidun solmun jälkeen. Solmu tulee tunnistaa sen elementtiarvoa vastaavalla indeksinumerolla.

Lisätäksesi ympyrälinkitetyn listan alkuun tai loppuun – eli kohtaan, johon ensimmäinen solmu lisättiin – noudata seuraavia ohjeita:

• Sinun on katkaistava olemassa oleva itselinkki olemassa olevaan solmuun
• Uuden solmun seuraava osoitin linkittää olemassa olevaan solmuun.
• Viimeisen solmun seuraava osoitin osoittaa lisättyyn solmuun.

HUOMAUTUS: Ympyrän alkua tai loppua merkitsevä osoitin voidaan siirtää mihin tahansa solmuun. Läpikulku palaa silti samaan solmuun, kuten tässä artikkelissa myöhemmin käsitellään.

Kohdan (a) i-iii vaiheet näytetään alla:

(Olemassa oleva solmu)

Vaihe 1) Katkaise olemassa oleva linkki

Vaihe 2) Luo eteenpäin linkki (uudesta solmusta olemassa olevaan solmuun)

Vaihe 3) Luo silmukkalinkki ensimmäiseen solmuun

Seuraavaksi yrität lisätä solmun jälkeen.

Lisää esimerkiksi ”ARVO2” ”ARVO0”-solmun jälkeen olettaen, että lähtöpiste on ”ARVO0”-solmu.

• Katkaise ensimmäisen ja toisen solmun välinen linkki ja aseta solmu, jonka väliin tulee ”VALUE2”.
• Ensimmäisen solmun seuraava osoitin linkittää uuteen solmuun, ja uuden solmun seuraava osoitin linkittää siihen, mikä oli aiemmin toinen solmu.
• Loput järjestelystä pysyy muuttumattomana. Kaikki solmut on uudelleenjärjestetty.tracitselleen kykeneviä.

HUOMAUTUS: Koska järjestely on syklinen, solmun lisäämismenettely on sama riippumatta siitä, minkä sijainnin valitset. Syklin sulkeva osoitin käyttäytyy kuten mikä tahansa muu listan osoitin.

Tämä näkyy alla:

(Sanotaan, että solmuja on vain kaksi. Tämä on triviaali tapaus)

Vaihe 1) Poista sisälinkki liitettyjen solmujen välillä

Vaihe 2) Yhdistä vasemmanpuoleinen solmu uuteen solmuun

Vaihe 3) Yhdistä uusi solmu oikeanpuoleiseen solmuun.

poisto OperaTUKSEN

Oletetaan, että kyseessä on kolmisolmuinen ympyrälinkitetty lista. Kaksi poistotapausta ovat:

• Nykyisen elementin poistaminen
• Poistaminen elementin jälkeen.

Poisto alussa/lopussa:

1. Siirry ensimmäiseen solmuun viimeisestä solmusta.
2. Poisto lopusta vaatii vain yhden läpikulkuvaiheen viimeisestä solmusta ensimmäiseen solmuun.
3. Poista linkki viimeisen ja ensimmäisen solmun välillä.
4. Linkitä viimeinen solmu ensimmäisen solmun seuraavaan elementtiin.
5. Vapauta ensimmäinen solmu.

(nykyinen kokoonpano)

Vaihe 1) Poista pyöreä linkki

Vaihe 2) Poista linkki ensimmäisen ja seuraavan välillä, linkitä viimeinen solmu ensimmäistä seuraavaan solmuun

Vaihe 3) Vapauta / vapauta ensimmäinen solmu

Poistaminen solmun jälkeen:

1. Käy läpi, kunnes seuraava solmu on poistettava solmu.
2. Siirrä seuraavaan solmuun asettamalla osoittimen edelliseen solmuun.
3. Yhdistä edellinen solmu nykyisen solmun jälkeiseen solmuun käyttämällä sen seuraavaa osoitinta.
4. Vapauta nykyinen (linkitetty) solmu.

Vaihe 1) Sanotaan, että meidän on poistettava solmu, jossa on "VALUE1".

Vaihe 2) Poista linkki edellisen ja nykyisen solmun välillä ja linkitä sitten edellinen solmu suoraan solmuun, johon nykyisen solmun seuraava osoitin osoittaa (solmu VALUE1:n jälkeen).

Vaihe 3) Vapauta tai vapauta nykyinen solmu.

Pyöreän linkitetyn luettelon läpikäynti

Kävelläksesi ympyrälinkitetyn listan läpi viimeisestä osoittimesta alkaen, tarkista ensin, onko viimeinen osoitin NULL. Jos se ei ole NULL, tarkista, onko listassa vain yksi alkio. Muussa tapauksessa kävele listaa väliaikaisen osoittimen kanssa, kunnes saavutat viimeisen osoittimen uudelleen, kuten alla olevassa animaatiossa on esitetty.

Pyöreän linkitetyn luettelon edut

Jotkut pyöreän linkitetyn luettelon eduista ovat:

1. Ei vaatimusta NULL-määrityksestä koodissa. Pyöreä luettelo ei koskaan osoita NULL-osoittimeen, ellei sitä ole kokonaan vapautettu.
2. Ympyrälinkitetyt listat ovat edullisia listan loppu -operaatioissa, koska niiden alku ja loppu ovat samat. Algorithms kuten round-robin-ajoitukset, voivat liikkua jonossa olevien prosessien läpi siististi kohtaamatta roikkuvia tai NULL-osoittimia.
3. Ympyrälinkitetty lista tukee edelleen kaikkia yksinkertaisesti linkitetyn listan tavallisia toimintoja. kaksinkertaisesti linkitetty lista voi jopa poistaa tarpeen täyspitkälle läpikäynnille elementin paikantamiseksi – pahimmassa tapauksessa kohde sijaitsee vastapäätä aloitusosoitinta, joten korkeintaan puolet listasta on käveltävä.

Pyöreän linkitetyn luettelon haitat

Pyöreän linkitetyn luettelon käytön haitat ovat alla:

1. Ympyrälistat ovat monimutkaisempia kuin yksittäin linkitetyt luettelot.
2. RevYmpyrälistan muodostaminen on monimutkaisempaa kuin yksinkertaisesti tai kahdesti linkitetyn listan kääntäminen päinvastaiseksi.
3. Jos silmukan päättämistä ei käsitellä huolellisesti, läpikulkukoodi voi ajautua äärettömään silmukkaan.
4. Listan lopun löytäminen ja oikeiden silmukan ohjausehtojen kirjoittaminen on vaikeampaa.
5. Alkuun lisääminen edellyttää koko listan läpikäymistä viimeisen solmun saavuttamiseksi (toteutuksen näkökulmasta).

Yksittäin linkitetty luettelo kiertokirjeenä linkitettynä luettelona

Sinua kannustetaan lukemaan ja toteuttamaan alla oleva C-koodi. Se havainnollistaa ympyrämäiseen, yksittäiseen linkitettyyn listaan ​​liittyvää osoittimen aritmetiikkaa.

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Koodin selitys:

1. Kaksi ensimmäistä koodiriviä ovat tarvittavat sisällytettävät otsikkotiedostot.
2. Seuraavassa osiossa määritellään kunkin itseensä viittaavan solmun rakenne. Se sisältää arvon ja osoittimen, jotka ovat samantyyppisiä kuin rakenne.
3. Jokainen rakenne-instanssi linkittyy muihin saman tyyppisiin rakenneobjekteihin.
4. On olemassa erilaisia ​​toimintoprototyyppejä:
   1. Elementin lisääminen tyhjään linkitettyyn luetteloon
   2. Asennus osoitteessa tällä hetkellä osoittanut pyöreän linkitetyn luettelon sijainti.
   3. Lisääminen tietyn jälkeen indeksoitu arvo linkitetyssä luettelossa.
   4. Poistaminen/poistaminen tietyn jälkeen indeksoitu arvo linkitetyssä luettelossa.
   5. Poistetaan pyöreän linkitetyn luettelon tällä hetkellä osoittamasta kohdasta
5. Viimeinen funktio tulostaa jokaisen elementin pyöreän läpikulun missä tahansa linkitetyn luettelon tilassa.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

Koodin selitys:

1. Varaa addToEmpty-koodille tyhjä solmu malloc()-funktiolla.
2. Sijoita saapuvat tiedot väliaikaiseen solmuun.
3. Määritä temp-solmu viimeiseksi ja aseta sen seuraava osoitin itseensä niin, että yksittäinen solmu osoittaa takaisin itseensä.
4. Palauttaa viimeisen osoittimen takaisin main() / application-kontekstiin.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Koodin selitys

1. Jos lista on tyhjä, siirrä se addToEmpty()-funktiolle ja palauta ohjausobjekti.
2. Luo väliaikainen solmu sijoitettavaksi nykyisen solmun jälkeen.
3. Yhdistä osoittimet yllä olevan kaavion mukaisesti.
4. Palauttaa viimeisen osoittimen, joka vastaa edellisessä funktiossa käytettyä kuviota.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Koodin selitys:

1. Jos lista on tyhjä, jätä hakuavain huomiotta, lisää nykyinen kohde listan ainoaksi solmuksi ja palauta control.
2. Jokaisessa do-while-silmukan iteraatiossa edellinen osoitin sisältää viimeksi läpikäydyn tuloksen.
3. Vasta sen jälkeen tapahtuu seuraava läpikulkuvaihe.
4. Do-while-funktio päättyy, kun kohdedata löytyy tai kun temp saavuttaa viimeisen osoittimen uudelleen. Seuraava koodilohko päättää, mitä löydetylle tiedolle tehdään.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Koodin selitys:

1. Jos koko lista on käyty läpi, mutta etsimääsi ei löydy, näytä viesti ”Elementtiä ei löydy” ja palauta ohjaus kutsujalle.
2. Jos kohdesolmu löytyy, varaa lisättävälle arvolle uusi solmu.
3. Linkki edellisen solmun uuteen solmuun ja linkitä uuden solmun seuraavan osoittimen temp-muuttujaan (läpikulkumuuttuja).
4. Tämä sijoittaa uuden elementin välittömästi kohdesolmun jälkeen ympyränmuotoisessa linkitetyssä listassa. Ohjaus palaa sitten kutsujalle.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Koodin selitys

1. Viimeisen (nykyisen) solmun poistamiseksi tarkista ensin, onko lista tyhjä. Jos on, yhtäkään elementtiä ei voida poistaa.
2. Temp-muuttuja siirtää yhden linkin eteenpäin.
3. Linkitä viimeinen osoitin ensimmäisen solmun jälkeen olevaan solmuun.
4. Vapauta väliaikainen osoitin linkittämättömän solmun vapauttamiseksi.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Koodin selitys

1. Kuten edellisessä poistofunktiossa, tarkista ensin, onko lista tyhjä. Jos on, yhtäkään elementtiä ei voida poistaa.
2. Kaksi viitteitä niille on määritetty tietyt paikat poistettavan elementin löytämiseksi.
3. Osoittimet siirtyvät eteenpäin yksi toisensa perään (edellinen polku väliaikainen).
4. Läpikulku jatkuu, kunnes kohdealkio löytyy tai seuraava osoitin saavuttaa jälleen viimeisen solmun.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

Ohjelman selitys

1. Jos koko linkitetty lista käydään läpi löytämättä kohdetta, näyttöön tulee viesti ”Elementtiä ei löydy”.
2. Muussa tapauksessa elementin linkitys puretaan ja se vapautetaan vaiheissa 3 ja 4.
3. Edellinen osoitin on linkitetty solmuun, johon temp-funktion seuraava osoitin osoittaa (poistettavaa osoitinta seuraava solmu).
4. Lämpötilaosoitin vapautetaan sitten.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Koodin selitys

1. Kurkistusläpikulku ei ole mahdollinen, jos solmuja on nolla – käyttäjän on ensin varattava tai lisättävä solmu.
2. Jos solmuja on vain yksi, läpikulkua ei tarvita — solmun sisältö tulostetaan suoraan eikä while-silmukkaa suoriteta.
3. Jos solmuja on useampi kuin yksi, temp tulostaa kaikki alkiot viimeiseen elementtiin asti.
4. Heti kun viimeinen elementti on saavutettu, silmukka päättyy ja funktio palauttaa ohjauksen main()-funktiolle.

Circular Linked List -sovellukset

• Round-robin-aikataulutuksen toteuttaminen järjestelmäprosesseissa ja kiertoajoitus nopeassa grafiikassa.
• Token-ring-ajoitus tietokoneverkoissa.
• Käytetään näyttöyksiköissä, kuten digitaalisissa myymälätauluissa, jotka vaativat jatkuvaa tiedon läpikulkua.

UKK