Egyszeresen linkelt lista vs duplán linkelt lista
A linkelt lista egy lineáris adatstruktúra, amely adatgyűjtemény tárolására szolgál. A csatolt lista külön-külön rendeli le a memóriát az elemeihez a saját memóriablokkjában, és a teljes szerkezetet úgy kapjuk meg, hogy ezeket az elemeket láncszemként kapcsoljuk össze. Az egyedileg összekapcsolt lista csomópontok sorozatából áll, és minden csomópont hivatkozással rendelkezik a sorozat következő csomópontjára. A duplán összekapcsolt lista csomópontok sorozatát tartalmazza, amelyben minden csomópont hivatkozást tartalmaz a következő csomópontra, valamint az előző csomópontra.
Egyedül linkelt lista
Egy egyedileg összekapcsolt lista minden eleméhez két mező tartozik, ahogy az 1. ábrán látható. Az adatmező tartalmazza a ténylegesen tárolt adatokat, a következő mező pedig a lánc következő elemére való hivatkozást. A hivatkozott lista első eleme a hivatkozott lista fejeként kerül tárolásra.
A 2. ábra három elemből álló, egyedileg összekapcsolt listát mutat be. Minden elem tárolja az adatait, és az utolsó kivételével minden elem a következő elemre való hivatkozást tárolja. Az utolsó elem a következő mezőjében null értéket tartalmaz. A lista bármely elemét elérheti úgy, hogy a fejléctől kezdi, és követi a következő mutatót, amíg el nem éri a kívánt elemet.
Duplán linkelt lista
A duplán linkelt lista minden eleme három mezővel rendelkezik, amint az a 3. ábrán látható. Az egyedileg összekapcsolt listához hasonlóan az adatmező tartalmazza a ténylegesen tárolt adatokat, a következő mező pedig a hivatkozást a lánc következő elemére. Ezenkívül az előző mező tartalmazza a hivatkozást a lánc előző elemére. A hivatkozott lista első eleme a hivatkozott lista fejeként kerül tárolásra.
A 4. ábra egy kétszeresen összekapcsolt listát mutat be három elemből. Az összes köztes elem hivatkozásokat tárol az első és az előző elemekre. A lista utolsó eleme null értéket tartalmaz a következő mezőjében, és a lista első eleme az előző mezőjében. A duplán linkelt listák az egyes elemek következő hivatkozásait követve haladhatnak előre, és hasonlóképpen visszafelé is az egyes elemek előző hivatkozásaival.
Mi a különbség az egyszeresen linkelt lista és a kétszeresen linkelt lista között?
Az egyszeresen hivatkozott lista minden eleme hivatkozást tartalmaz a lista következő elemére, míg a duplán linkelt lista minden eleme a következő elemre, valamint a lista előző elemére utal. A duplán linkelt listák több helyet igényelnek a lista minden eleméhez, és az olyan elemi műveletek, mint a beszúrás és a törlés, bonyolultabbak, mivel két hivatkozással kell foglalkozniuk. A duplahivatkozásos listák azonban egyszerűbb manipulációt tesznek lehetővé, mivel lehetővé teszik a lista előre és hátra történő bejárását.
