Egyedül összekapcsolt lista vs kétszeresen összekapcsolt lista
A kapcsolt lista egy lineáris adatstruktúra, amelyet egy adatgyűjtemény tárolására használnak. Egy összekapcsolt lista külön memóriát oszt elemeihez a saját memóriablokkjában, és a teljes struktúrát úgy kapjuk meg, hogy ezeket az elemeket összekapcsoljuk egy láncban. Egyenként összekapcsolt lista csomópontok sorozatából áll, és minden csomópont hivatkozik a sorozat következő csomópontjára. A kétszeresen ö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.
Egyszerűen összekapcsolt lista
Az egyenként összekapcsolt lista minden elemének két mezője van, amint azt az 1. ábra mutatja. Az adatmező tartalmazza a tényleges tárolt adatokat, a következő mező pedig a lánc következő elemére való hivatkozást tartalmazza. A csatolt lista első elemét a csatolt lista fejeként tárolja.
A 2. ábra három elemből álló, egymással összekapcsolt listát ábrázol. Minden elem tárolja az adatait, az utolsó kivételével minden elem hivatkozást tárol a következő elemre. Az utolsó elem null értéket tartalmaz a következő mezőjében. A lista bármely eleméhez úgy lehet hozzáférni, hogy az elejétől kezdve a következő mutatót követi, amíg meg nem felel a szükséges elemnek.
Kétségkívül összekapcsolt lista
A kétszeresen összekapcsolt lista minden elemének három mezője van, amint azt a 3. ábra mutatja. Az önállóan összekapcsolt listához hasonlóan az adatmező is a tényleges tárolt adatokat tartalmazza, a következő mező pedig a lánc következő elemére való hivatkozást tartalmazza. Ezenkívül az előző mező tartalmazza a hivatkozást a lánc előző elemére. A csatolt lista első elemét a csatolt lista fejeként tárolja.
A 4. ábra kétszeresen összekapcsolt listát ábrázol, három elemmel. Az összes köztes elem tárolja az első és az előző elemek hivatkozásait. A lista utolsó eleme null értéket tartalmaz a következő mezőjében, a lista első eleme pedig null értéket tartalmaz az előző mezőjében. A kétszeresen összekapcsolt listát előre lehet haladni, ha követjük az egyes elemek következő hivatkozásait, és hasonlóan visszafelé is haladhatunk az egyes elemek előző hivatkozásai segítségével.
Mi a különbség az Egyszerűen összekapcsolt lista és a Duplán összekapcsolt lista között?
Az egyesével összekapcsolt lista minden eleme tartalmaz hivatkozást a lista következő elemére, míg a kettősen összekapcsolt lista minden eleme tartalmaz hivatkozásokat a lista következő elemére, valamint a lista előző elemére. A kétszeresen összekapcsolt listákhoz több hely szükséges a lista minden eleméhez, és az olyan alapvető műveletek, mint a beillesztés és a törlés bonyolultabbak, mivel két hivatkozással kell foglalkozniuk. De a kettős linklisták megkönnyítik a manipulációt, mivel lehetővé teszik a lista előre és hátra történő haladását.