Körkörös linkelt lista: Előnyök és Hátrányok

Mi az a körkörös linkelt lista?

A kör alakú linkelt lista olyan csomópontok sorozata, amelyek úgy vannak elrendezve, hogy minden csomópont visszavezethető önmagához. Itt a „csomópont” egy önreferencia elem, amely egy vagy két csomópontra mutat a közvetlen közelében.

Az alábbiakban egy kör alakú linkelt lista látható 3 csomóponttal.

Körkörös linkelt lista

Itt láthatja, hogy minden csomópont visszavezethető önmagához. A fent látható példa egy körkörös, egyedileg összekapcsolt lista.

Megjegyzés: A legegyszerűbb körkörös linkelt lista egy olyan csomópont, amely csak önmagát követi nyomon, az ábrán látható módon

Körkörös linkelt lista

alapvető Operaa körlevélben hivatkozott listákban

A kör alakú linkelt lista alapvető műveletei a következők:

  1. beszúrás
  2. Törlés és
  3. A bejárás
  • A beszúrás az a folyamat, amelynek során egy csomópontot helyezünk el a körkörös hivatkozási lista egy meghatározott pozíciójában.
  • A törlés egy meglévő csomópont eltávolításának folyamata a hivatkozott listáról. A csomópont azonosítható értékének előfordulása vagy pozíciója alapján.
  • A körkörös csatolt lista bejárása a teljes csatolt lista tartalmának megjelenítése és a forráscsomóponthoz való visszatérés folyamata.

A következő részben megismerheti a csomópontok beszúrását és a lehetséges beszúrási típusokat egy körkörös, egyszeri hivatkozásos listába.

beszúrás OperaCIÓ

Kezdetben létre kell hoznia egy csomópontot, amely önmagára mutat, amint az ezen a képen látható. E csomópont nélkül a beillesztés létrehozza az első csomópontot.

beszúrás OperaCIÓ

Ezután két lehetőség van:

  • Beszúrás a körkörös csatolt lista aktuális helyére. Ez megfelel a szabályos egyes számban hivatkozott lista végének elejére történő beszúrásnak. Egy kör alakú linkelt listában az eleje és a vége megegyezik.
  • Beszúrás egy indexelt csomópont után. A csomópontot az elemértékének megfelelő indexszámmal kell azonosítani.

A körkörös linkelt lista elejére/végére történő beszúráshoz, vagyis arra a helyre, ahol az első csomópont hozzáadásra került,

  • Meg kell szakítania a meglévő önhivatkozást a meglévő csomóponthoz
  • Az új csomópont következő mutatója a meglévő csomópontra fog hivatkozni.
  • Az utolsó csomópont következő mutatója a beillesztett csomópontra mutat.

MEGJEGYZÉS: A token master vagy a kör eleje/vége mutató módosítható. Továbbra is visszatér ugyanahhoz a csomóponthoz egy bejáráskor, amelyet előre megbeszélünk.

Az (a) i-iii lépések az alábbiakban láthatók:

beszúrás OperaCIÓ

(Meglévő csomópont)

beszúrás OperaCIÓ

1. LÉPÉS) Törje meg a meglévő linket

beszúrás OperaCIÓ

2. LÉPÉS) Továbbító hivatkozás létrehozása (új csomópontról egy meglévő csomópontra)

beszúrás OperaCIÓ

3. LÉPÉS) Hozzon létre egy hurokhivatkozást az első csomóponthoz

Ezután egy csomópont után próbálja meg beszúrni.

Például illesszük be az „VALUE2”-t a „VALUE0”-ás csomópont után. Tegyük fel, hogy a kiindulási pont az „VALUE0” csomópont.

  • Meg kell szakítania az első és a második csomópont közötti vonalat, és el kell helyeznie a csomópontot az „VALUE2” értékkel közéjük.
  • Az első csomópont következő mutatójának ehhez a csomóponthoz, a következő csomópont következő mutatójának pedig a korábbi második csomóponthoz kell kapcsolódnia.
  • Az elrendezés többi része változatlan marad. Minden csomópont visszavezethető önmagához.

MEGJEGYZÉS: Mivel létezik ciklikus elrendezés, a csomópont beszúrása ugyanazt az eljárást jelenti bármely csomópontnál. A ciklust befejező mutató ugyanúgy befejezi a ciklust, mint bármely más csomópont.

Ez az alábbiakban látható:

beszúrás OperaCIÓ

(Tegyük fel, hogy csak két csomópont van. Ez triviális eset)

beszúrás OperaCIÓ

1. LÉPÉS) Távolítsa el a belső kapcsolatot a csatlakoztatott csomópontok között

beszúrás OperaCIÓ

2. LÉPÉS) Csatlakoztassa a bal oldali csomópontot az új csomóponthoz

beszúrás OperaCIÓ

3. LÉPÉS) Csatlakoztassa az új csomópontot a jobb oldali csomóponthoz.

törlés OperaCIÓ

Tételezzünk fel egy 3 csomópontos kör alakú linkelt listát. A törlés eseteit az alábbiakban ismertetjük:

  • Az aktuális elem törlése
  • Elem utáni törlés.

Törlés az elején/végén:

  1. Haladjon át az első csomópontra az utolsó csomóponttól.
  2. A végétől való törléshez csak egy bejárási lépésnek kell lennie, az utolsó csomóponttól az első csomópontig.
  3. Törölje az utolsó csomópont és a következő csomópont közötti kapcsolatot.
  4. Kapcsolja össze az utolsó csomópontot az első csomópont következő elemével.
  5. Szabadítsa fel az első csomópontot.

törlés OperaCIÓ

(Meglévő beállítás)

törlés OperaCIÓ

STEP 1) Távolítsa el a kör alakú linket

törlés OperaCIÓ

2. LÉPÉS) Távolítsa el a kapcsolatot az első és a következő között, kapcsolja az utolsó csomópontot az elsőt követő csomóponthoz

törlés OperaCIÓ

3. LÉPÉS) Az első csomópont felszabadítása/kiosztása

Törlés egy csomópont után:

  1. Haladjon addig, amíg a következő csomópont lesz a törölni kívánt csomópont.
  2. Ugrás a következő csomópontra, mutatót helyezve az előző csomópontra.
  3. Csatlakoztassa az előző csomópontot a jelenlegi csomópont utáni csomóponthoz a következő mutató segítségével.
  4. Szabadítsa fel az aktuális (lekapcsolt) csomópontot.

törlés OperaCIÓ

1. LÉPÉS) Tegyük fel, hogy törölnünk kell egy „VALUE1” csomópontot.

törlés OperaCIÓ

2. LÉPÉS) Távolítsa el a kapcsolatot az előző csomópont és az aktuális csomópont között. Kapcsolja össze az előző csomópontját a következő csomóponttal, amelyre az aktuális csomópont mutat (VALUE1 értékkel).

törlés OperaCIÓ

3. LÉPÉS) Szabadítsa fel vagy oldja fel az aktuális csomópontot.

Egy körkörös linkelt lista bejárása

Ha körkörösen csatolt listát szeretne bejárni, az utolsó mutatótól kezdve, ellenőrizze, hogy maga az utolsó mutató NULL-e. Ha ez a feltétel hamis, ellenőrizze, hogy csak egy elem van-e. Ellenkező esetben egy ideiglenes mutató segítségével haladjon az utolsó mutatóig, vagy annyiszor, ahányszor szükséges, ahogy az alábbi GIF-en látható.

Egy körkörös linkelt lista bejárása

A körkörös linkelt lista előnyei

A körkörös linkelt listák néhány előnye:

  1. A kódban nincs előírás NULL hozzárendelésre. A körkörös lista soha nem mutat NULL mutatót, hacsak nincs teljesen felszabadítva.
  2. A kör alakú linkelt listák előnyösek a végműveletek számára, mivel a kezdet és a vége egybeesik. Algorithms mint például a Round Robin ütemezés, szépen kiküszöbölheti azokat a folyamatokat, amelyek körkörösen sorakoznak anélkül, hogy lógó vagy NULL hivatkozási mutatókkal találkoznának.
  3. A körkörös linkelt lista az egyszeresen csatolt lista összes szokásos funkcióját is ellátja. Valójában kör alakú duplán linkelt listák Az alábbiakban tárgyalt módszer akár teljes hosszúságú bejárás szükségességét is kiküszöbölheti egy elem helyének meghatározásához. Ez az elem legfeljebb csak pontosan ellentétes lenne a kezdettel, és csak a linkelt lista felét teszi ki.

A körkörös linkelt lista hátrányai

A kör alakú linkelt lista használatának hátrányai az alábbiak:

  1. A körkörös listák összetettek ahhoz képest egyedileg kapcsolódó listák.
  2. RevA körkörös lista erse összetett az egyszeres vagy dupla listákhoz képest.
  3. Ha nem kezeljük óvatosan, a kód végtelen ciklusban mehet.
  4. Nehezebb megtalálni a lista végét és a hurokvezérlést.
  5. Indításkor beszúrva a teljes listát kell bejárnunk, hogy megtaláljuk az utolsó csomópontot. (Megvalósítási perspektíva)

Egyedül linkelt lista körkörös linkelt listaként

Javasoljuk, hogy próbálja meg elolvasni és megvalósítani az alábbi kódot. Bemutatja a körkörös hivatkozású listákhoz társított mutató aritmetikát.

#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()
{
...

Egyedül linkelt lista

A kód magyarázata:

  1. A kód első két sora a szükséges fejlécfájlok.
  2. A következő rész az egyes önreferenciális csomópontok szerkezetét írja le. A szerkezettel azonos típusú értéket és mutatót tartalmaz.
  3. Mindegyik struktúra ismételten hivatkozik az azonos típusú szerkezeti objektumokra.
  4. Különböző funkciók prototípusai léteznek:
    1. Elem hozzáadása egy üres linkelt listához
    2. Beillesztés a jelenleg mutatott kör alakú linkelt lista helyzete.
    3. Beszúrás egy adott után indexelt érték a linkelt listában.
    4. Eltávolítás/törlés egy adott után indexelt érték a linkelt listában.
    5. Eltávolítás egy körkörös csatolt lista aktuális pontjában
  5. Az utolsó függvény minden elemet körkörös bejárással nyomtat ki a hivatkozott lista bármely állapotában.
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)

Egyedül linkelt lista

A kód magyarázata:

  1. Az addEmpty kódhoz a malloc függvény segítségével foglaljon le egy üres csomópontot.
  2. Ehhez a csomóponthoz helyezze az adatokat a temp változóba.
  3. Az egyetlen változó hozzárendelése és összekapcsolása a temp változóval
  4. Az utolsó elem visszaállítása a main() / application kontextusba.
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;
…

Egyedül linkelt lista

A kód magyarázata

  1. Ha nincs beszúrható elem, akkor ügyeljen arra, hogy hozzáadjon egy üres listához, és adja vissza a vezérlőt.
  2. Hozzon létre egy ideiglenes elemet, amelyet az aktuális elem után helyez el.
  3. Kapcsolja össze a mutatókat az ábrán látható módon.
  4. Az utolsó mutató visszaállítása az előző függvényhez hasonlóan.
...
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");
...

Egyedül linkelt lista

A kód magyarázata:

  1. Ha nincs elem a listában, hagyja figyelmen kívül az adatokat, adja hozzá az aktuális elemet a lista utolsó elemeként, és adja vissza a vezérlőt
  2. A do-while ciklus minden iterációja esetén győződjön meg arról, hogy van egy előző mutató, amely az utoljára bejárt eredményt tartalmazza.
  3. Csak ezután következhet be a következő átjárás.
  4. Ha az adat megtalálható, vagy a temp visszaáll az utolsó mutatóig, a do-while leáll. A kód következő része eldönti, hogy mit kell tenni az elemmel.
...
    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)
...

Egyedül linkelt lista

A kód magyarázata:

  1. Ha a teljes listát bejárták, de az elem nem található, jelenítse meg az „elem nem található” üzenetet, majd adja vissza az irányítást a hívónak.
  2. Ha található egy csomópont, és/vagy a csomópont még nem az utolsó csomópont, akkor hozzon létre egy új csomópontot.
  3. Link az előző csomópont az új csomóponttal. Kapcsolja össze az aktuális csomópontot a temp-mal (a bejárási változóval).
  4. Ez biztosítja, hogy az elem egy adott csomópont után kerüljön a körkörös hivatkozási listában. Térjen vissza a hívóhoz.
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)

Egyedül linkelt lista

A kód magyarázata

  1. Csak az utolsó (aktuális) csomópont eltávolításához ellenőrizze, hogy ez a lista üres-e. Ha igen, akkor egyetlen elem sem távolítható el.
  2. A temp változó csak egy linket halad előre.
  3. Kapcsolja össze az utolsó mutatót az első utáni mutatóval.
  4. Szabadítsa fel a hőmérséklet mutatót. Felszabadítja a nem összekapcsolt utolsó mutatót.
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");
...

Egyedül linkelt lista

A kód magyarázata

  1. Az előző eltávolítási funkcióhoz hasonlóan ellenőrizze, hogy nincs-e elem. Ha ez igaz, akkor egyetlen elem sem távolítható el.
  2. mutatók meghatározott pozíciók vannak hozzárendelve a törölni kívánt elem megkereséséhez.
  3. A mutatók előre vannak helyezve, egymás mögött. (előző a hőmérséklet mögött)
  4. A folyamat addig folytatódik, amíg meg nem talál egy elemet, vagy a következő elem vissza nem lép az utolsó mutatóhoz.
    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;	

Egyedül linkelt lista

A program magyarázata

  1. Ha az elemet a teljes csatolt lista bejárása után találták meg, hibaüzenet jelenik meg, amely szerint az elem nem található.
  2. Ellenkező esetben az elem szétválasztása és felszabadítása a 3. és 4. lépésben történik.
  3. Az előző mutató a törölni kívánt elem (temp) által „következőként” mutatott címhez kapcsolódik.
  4. A hőmérséklet-mutató ezért felszabadul és felszabadul.
...
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;
    }
}

Egyedül linkelt lista

A kód magyarázata

  1. A betekintés vagy bejárás nem lehetséges, ha nincs szükség nullára. A felhasználónak ki kell osztania vagy be kell illesztenie egy csomópontot.
  2. Ha csak egy csomópont van, akkor nem kell bejárni, a csomópont tartalma kinyomtatható, és a while ciklus nem fut le.
  3. Ha egynél több csomópont van, akkor a temp kiírja az összes elemet az utolsó elemig.
  4. Abban a pillanatban, amikor elérjük az utolsó elemet, a ciklus véget ér, és a függvény visszaadja a fő függvény hívását.

Alkalmazások a körlevél linkelt lista

  • A kör-robin ütemezés megvalósítása a rendszerfolyamatokban és a körkörös ütemezés a nagy sebességű grafikákban.
  • Token rings ütemezés számítógépes hálózatokban.
  • Olyan megjelenítő egységekben használják, mint a bolti táblák, amelyek folyamatos adatbejárást igényelnek.