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

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

A körkörös láncolt lista csomópontok sorozata, amelyek úgy vannak elrendezve, hogy minden csomópont újra és újra megjeleníthető.tracönmagára hivatkozó elem. Minden „csomópont” egy önmagára hivatkozó elem, amely egy vagy két, a közvetlen közelében lévő csomópontra mutató mutatókkal rendelkezik.

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

Itt látható, hogy minden csomópont újra vantracönmagának is elérhető. A fenti példa egy kör alakú, egyszeresen láncolt lista.

Megjegyzés: A legegyszerűbb körkörös láncolt lista egyetlen csomópont, amelynek a következő mutatója tracvisszaáll önmagához, ahogy az alább látható.

alapvető Operakörkörös láncolt listákban

Egy körkörös láncolt listán a három alapvető művelet a következő:

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.
• Egy körkörös láncolt lista bejárása az a folyamat, amelynek során a teljes láncolt lista tartalmát megjelenítjük, majd újraértelmezzük.tracvissza a forráscsomópontra.

A következő szakasz elmagyarázza, hogyan működik a beszúrás, és milyen kétféle beszúrás lehetséges egy körkörös, egyszeresen láncolt listában.

beszúrás OperaCIÓ

Először létrehozol egy csomópontot, amelynek a következő mutatója visszafelé mutat önmagára, ahogy az alább látható. E kezdőcsomópont nélkül az első beszúrt csomópont lesz a lista első csomópontja.

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

• Beszúrás a körkörös láncolt lista aktuális pozíciójába. Ez egy szabályos, egyszeresen láncolt lista elejére vagy végére történő beszúrásnak felel meg – egy körkörös láncolt listában a kezdet és a vég ugyanaz a pont.
• 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 láncolt lista elejére vagy végére – azaz oda, ahová az első csomópontot hozzáadtuk – a beszúráshoz kövesse az alábbi lépéseket:

• 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 kör kezdetét vagy végét jelző mutató bármelyik csomóponthoz hozzárendelhető. A bejárás továbbra is ugyanarra a csomópontra tér vissza, amint azt a cikk későbbi részében tárgyaljuk.

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

(Meglévő csomópont)

Step 1) Törje meg a meglévő linket

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

Step 3) 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 illessze be a „VALUE2” értéket a „VALUE0”-t tartalmazó csomópont után, feltételezve, hogy a kiindulópont a „VALUE0”-t tartalmazó csomópont.

• Szakítsa meg az első és a második csomópont közötti kapcsolatot, és helyezze el a „VALUE2” értékű csomópontot közöttük.
• Az első csomópont következő mutatója az új csomóponthoz kapcsolódik, az új csomópont következő mutatója pedig ahhoz, ami korábban a második csomópont volt.
• Az elrendezés többi része változatlan marad. Minden csomópont újra vantracképesek maguknak.

MEGJEGYZÉS: Mivel az elrendezés ciklikus, a csomópont beszúrásának eljárása azonos, függetlenül attól, hogy melyik pozíciót választja. A ciklust lezáró mutató úgy viselkedik, mint bármely más mutató a listában.

Ez az alábbiakban látható:

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

Step 1) Távolítsa el a belső kapcsolatot a csatlakoztatott csomópontok között

Step 2) Csatlakoztassa a bal oldali csomópontot az új csomóponthoz

Step 3) Csatlakoztassa az új csomópontot a jobb oldali csomóponthoz.

törlés OperaCIÓ

Tegyük fel, hogy egy 3 csomópontú cirkuláris láncolt lista. A két törlési eset a következő:

• 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éről történő törlés csak egyetlen bejárási lépést igényel, az utolsó csomóponttól az első csomópontig.
3. Töröld a kapcsolatot az utolsó és az első csomópont között.
4. Kapcsolja össze az utolsó csomópontot az első csomópont következő elemével.
5. Szabadítsa fel az első csomópontot.

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

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

Step 2) 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

Step 3) Az első csomópont felszabadítása / felszabadítása

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

1. Addig halad, amíg a következő csomópont nem lesz a törlendő 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.

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

Step 2) Távolítsa el a kapcsolatot az előző és az aktuális csomópont között, majd kösse össze az előző csomópontot közvetlenül azzal a csomóponttal, amelyre az aktuális csomópont következő mutatója mutat (a VALUE1 utáni csomópont).

Step 3) Szabadítsa fel vagy oldja fel az aktuális csomópontot.

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

Egy körkörös láncolt lista utolsó mutatóból kiinduló bejárásához először ellenőrizzük, hogy az utolsó mutató NULL-e. Ha nem NULL, ellenőrizzük, hogy a lista csak egy elemet tartalmaz-e. Ellenkező esetben egy ideiglenes mutatóval járjuk be a listát, amíg el nem érjük az utolsó mutatót, ahogy az az alábbi animáción is látható.

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örkörös láncolt listák előnyösek a listavég-műveletekhez, mivel a kezdet és a vég egybeesik. Algorithms például a körforgásos ütemezés tisztán mozoghat a sorban álló folyamatokon, lógó vagy NULL mutatókba ütközés nélkül.
3. Egy körkörös láncolt lista továbbra is támogatja az egyszeresen láncolt lista összes szabályos műveletét. kétszeresen láncolt lista akár kiküszöbölheti a teljes hosszúságú bejárás szükségességét egy elem megtalálásához – a legrosszabb esetben a cél a kezdőmutatóval szemben található, így legfeljebb a lista felét kell bejárni.

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örlisták összetettebbek, mint egyedileg kapcsolódó listák.
2. RevEgy körkörös lista létrehozása bonyolultabb, mint egy egyszeresen vagy kétszeresen láncolt lista megfordítása.
3. Ha a ciklus lezárását nem kezelik körültekintően, a bejárási kód végtelen ciklusba kerülhet.
4. Nehezebb megtalálni a lista végét és helyes ciklusvezérlési feltételeket írni.
5. A legelejére történő beszúrás megköveteli a teljes lista bejárását az utolsó csomópont eléréséhez (megvalósítási szempontból).

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

Javasoljuk, hogy olvasd el és implementáld az alábbi C kódot. Ez egy körkörös, egyszeresen láncolt listához tartozó mutatóaritmetikát szemlélteti.

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

A kód magyarázata:

1. A kód első két sora a szükséges fejlécfájlok.
2. A következő szakasz az egyes önhivatkozó csomópontok szerkezetét definiálja. Tartalmaz egy értéket és egy, a struktúrával megegyező típusú mutatót.
3. Minden struktúra példány más, azonos típusú struktúra objektumokhoz kapcsolódik.
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)

A kód magyarázata:

1. Az addToEmpty kódhoz foglalj le egy üres csomópontot a malloc() függvénnyel.
2. Helyezze a bejövő adatokat az ideiglenes csomópontba.
3. Rendeld a temp csomópontot utolsónak, és állítsd be a következő mutatóját önmagára, hogy az egyetlen csomópont visszamutasson önmagára.
4. Visszaadja az utolsó mutatót a main() / alkalmazás 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;
…

A kód magyarázata

1. Ha a lista üres, add át az addToEmpty() függvénynek, és add vissza a vezérlést.
2. Hozz létre egy ideiglenes csomópontot, amelyet a jelenlegi csomópont után kell elhelyezni.
3. Kösd össze a mutatókat a fenti ábrán látható módon.
4. Visszaadja az utolsó mutatót, amely illeszkedik az előző függvényben használt mintához.

...
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");
...

A kód magyarázata:

1. Ha a lista üres, hagyja figyelmen kívül a keresési kulcsot, adja hozzá az aktuális elemet egyetlen csomópontként a listában, és adja vissza a control értéket.
2. A do-while ciklus minden iterációjában egy előző mutató tartalmazza az utoljára bejárt eredményt.
3. Csak ezután történik a következő bejárási lépés.
4. A do-while függvény akkor ér véget, amikor a céladatot megtalálja a rendszer, vagy amikor a temp ismét eléri az utolsó mutatót. A következő kódblokk eldönti, hogy mit tegyen a megtalált 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)
...

A kód magyarázata:

1. Ha a teljes listán már túljutott, de a keresett elem nem található, akkor jelenítsen meg egy „Elem nem található” üzenetet, és adja vissza a vezérlést a hívónak.
2. Ha a célcsomópont megtalálható, akkor a beszúrandó értékhez új csomópontot kell lefoglalni.
3. Link az előző csomópontot az új csomóponthoz csatolja, és az új csomópont következő mutatóját a temp változóhoz (a bejárási változóhoz) csatolja.
4. Ez az új elemet közvetlenül a célcsomópont után helyezi el a körkörös láncolt listában. A vezérlés ezután visszatér 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)

A kód magyarázata

1. Az utolsó (aktuális) csomópont eltávolításához először ellenőrizd, hogy a lista üres-e. Ha igen, akkor egyetlen elem sem távolítható el.
2. A temp változó egy láncszemet előre mozdít.
3. Kapcsolja össze az utolsó mutatót az első csomópont utáni csomóponttal.
4. Szabadítsa fel az ideiglenes mutatót a leválasztott csomópont felszabadításához.

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");
...

A kód magyarázata

1. Az előző eltávolító függvényhez hasonlóan először ellenőrizzük, hogy a lista üres-e. Ha igen, akkor egyetlen elem sem távolítható el.
2. Kettő 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 egymás után haladnak előre (előző nyomvonalak ideiglenes).
4. A bejárás addig folytatódik, amíg a célelem meg nem található, vagy a következő mutató ismét el nem éri az utolsó csomópontot.

    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;

A program magyarázata

1. Ha a teljes láncolt listán a célpont megtalálása nélkül haladunk végig, akkor az „Elem nem található” üzenet jelenik meg.
2. Ellenkező esetben az elem leválasztásra és felszabadításra kerül a 3. és 4. lépésben.
3. Az előző mutató ahhoz a csomóponthoz kapcsolódik, amelyre a temp következő mutatója mutat (a törölt csomópont utáni).
4. A hőmérséklet-mutató ezután 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;
    }
}

A kód magyarázata

1. A betekintési bejárás nem lehetséges, ha nulla csomópont van – a felhasználónak először le kell foglalnia vagy be kell szúrnia egy csomópontot.
2. Ha csak egy csomópont van, akkor nincs szükség bejárásra – a csomópont tartalma közvetlenül kiíródik, és a while ciklus nem hajtódik végre.
3. Ha egynél több csomópont van, a temp függvény az utolsó elemig kinyomtatja az összes elemet.
4. Abban a pillanatban, amikor a ciklus eléri az utolsó elemet, a ciklus véget ér, és a függvény visszaadja a vezérlést a main()-nek.

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 gyűrűs ütemezés számítógépes hálózatokban.
• Olyan kijelzőegységekben használják, mint például a digitális üzletek táblái, amelyek folyamatos adatfeldolgozást igényelnek.

GYIK