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.
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
alapvető Operaa körlevélben hivatkozott listákban
A kör alakú linkelt lista alapvető műveletei a következők:
- beszúrás
- Törlés és
- 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.
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:
(Meglévő csomópont)
1. LÉPÉS) Törje meg a meglévő linket
2. LÉPÉS) Továbbító hivatkozás létrehozása (új csomópontról egy meglévő csomópontra)
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ó:
(Tegyük fel, hogy csak két csomópont van. Ez triviális eset)
1. LÉPÉS) Távolítsa el a belső kapcsolatot a csatlakoztatott csomópontok között
2. LÉPÉS) Csatlakoztassa a bal oldali csomópontot az új csomóponthoz
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:
- Haladjon át az első csomópontra az utolsó csomóponttól.
- 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.
- Törölje az utolsó csomópont és a következő csomópont közötti kapcsolatot.
- Kapcsolja össze az utolsó csomópontot az első csomópont következő elemével.
- Szabadítsa fel az első csomópontot.
(Meglévő beállítás)
STEP 1) Távolítsa el a kör alakú linket
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
3. LÉPÉS) Az első csomópont felszabadítása/kiosztása
Törlés egy csomópont után:
- Haladjon addig, amíg a következő csomópont lesz a törölni kívánt csomópont.
- Ugrás a következő csomópontra, mutatót helyezve az előző csomópontra.
- Csatlakoztassa az előző csomópontot a jelenlegi csomópont utáni csomóponthoz a következő mutató segítségével.
- Szabadítsa fel az aktuális (lekapcsolt) csomópontot.
1. LÉPÉS) Tegyük fel, hogy törölnünk kell egy „VALUE1” csomópontot.
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).
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ó.
A körkörös linkelt lista előnyei
A körkörös linkelt listák néhány előnye:
- 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.
- 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.
- 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:
- A körkörös listák összetettek ahhoz képest egyedileg kapcsolódó listák.
- RevA körkörös lista erse összetett az egyszeres vagy dupla listákhoz képest.
- Ha nem kezeljük óvatosan, a kód végtelen ciklusban mehet.
- Nehezebb megtalálni a lista végét és a hurokvezérlést.
- 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() { ...
A kód magyarázata:
- A kód első két sora a szükséges fejlécfájlok.
- 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.
- Mindegyik struktúra ismételten hivatkozik az azonos típusú szerkezeti objektumokra.
- Különböző funkciók prototípusai léteznek:
- Elem hozzáadása egy üres linkelt listához
- Beillesztés a jelenleg mutatott kör alakú linkelt lista helyzete.
- Beszúrás egy adott után indexelt érték a linkelt listában.
- Eltávolítás/törlés egy adott után indexelt érték a linkelt listában.
- Eltávolítás egy körkörös csatolt lista aktuális pontjában
- 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:
- Az addEmpty kódhoz a malloc függvény segítségével foglaljon le egy üres csomópontot.
- Ehhez a csomóponthoz helyezze az adatokat a temp változóba.
- Az egyetlen változó hozzárendelése és összekapcsolása a temp változóval
- 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; …
A kód magyarázata
- Ha nincs beszúrható elem, akkor ügyeljen arra, hogy hozzáadjon egy üres listához, és adja vissza a vezérlőt.
- Hozzon létre egy ideiglenes elemet, amelyet az aktuális elem után helyez el.
- Kapcsolja össze a mutatókat az ábrán látható módon.
- 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"); ...
A kód magyarázata:
- 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
- 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.
- Csak ezután következhet be a következő átjárás.
- 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) ...
A kód magyarázata:
- 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.
- 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.
- 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).
- 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)
A kód magyarázata
- 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.
- A temp változó csak egy linket halad előre.
- Kapcsolja össze az utolsó mutatót az első utáni mutatóval.
- 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"); ...
A kód magyarázata
- 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.
- mutatók meghatározott pozíciók vannak hozzárendelve a törölni kívánt elem megkereséséhez.
- A mutatók előre vannak helyezve, egymás mögött. (előző a hőmérséklet mögött)
- 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;
A program magyarázata
- 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ó.
- Ellenkező esetben az elem szétválasztása és felszabadítása a 3. és 4. lépésben történik.
- Az előző mutató a törölni kívánt elem (temp) által „következőként” mutatott címhez kapcsolódik.
- 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; } }
A kód magyarázata
- 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.
- Ha csak egy csomópont van, akkor nem kell bejárni, a csomópont tartalma kinyomtatható, és a while ciklus nem fut le.
- Ha egynél több csomópont van, akkor a temp kiírja az összes elemet az utolsó elemig.
- 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.