Láncolt lista (adatszerkezet)

A Programozás Wiki wikiből

A programozásban használt legegyszerűbb adatszerkezetek egyike, amely tetszőleges - ráadásul akár széles skálán változó - számú elem tárolására, gyűjtésére ad lehetőséget. Nevét onnan kapta, hogy a lista elemei egymásra mutató hivatkozásokat tartalmaznak, aminek köszönhetően egy lánc szemeihez hasonlóan egymáshoz kapcsolódva képezik a listát.

A láncolt lista nagy előnye a tömbbel szemben, hogy eltérő típusú és méretű elemeket is képes magába foglalni, amelyek ráadásul a memóriában nem feltétlenül kell, hogy szekvenciálisan - és a listában szereplő sorrendben - helyezkedjenek el, hanem tetszőleges módon szétszórva lehet tárolni őket. További előnye - az egyszerű listával szemben is -, hogy a lista módosítása, azaz elemek törlése, új elem beszúrása vagy a meglévők átrendezése mindössze a hivatkozások módosításával megoldható, amely jóval erőforrástakarékosabb megoldás maguk az elemek - vagy lista esetében az elemekre mutató hivatkozások sokaságának - mozgatásánál és átrendezésénél ha ez a művelet gyakran történik, az elemekből sok van és/vagy ha utóbbiak néhány bájtnál nagyobb adatterületen kerülnek tárolásra.

A láncolt lista hátránya, hogy - szemben pl. a tömbbel és az egyszerű listával - az elemek véletlenszerűen ill. pusztán sorszámuk alapján közvetlenül nem, csak a lista (részleges) bejárásával érhetők el és címezhetők meg, így az ilyen hozzáférést igénylő algoritmusokban történő felhasználás általában jóval lassabb működést eredményez, mintha egyszerű listát vagy tömböt alkalmaznánk az adatok tárolására.

Egyszerű (egyirányú) láncolt lista[szerkesztés]

Az egyszerű láncolt lista esetében a lista minden egyes eleme kizárólag a lista sorban következő elemére mutató hivatkozást tartalmaz. Ennek a megoldásnak az előnye a lista garantált konzisztenciája, egyszerű kezelése és csekély tárigénye. Hátrányai, hogy a listában mindig csak egy irányban - a láncolás irányában - lehet mozogni, korábbi elemekre csak úgy lehet visszatérni, ha a lista elejéről ismét elkezdünk végiglépkedni rajta.

Duplán láncolt lista[szerkesztés]

A duplán láncolt lista esetében a lista minden egyes eleme az őt követő mellett az őt megelőző elemre is tartalmaz hivatkozást. Ez utóbbi lehetővé teszi a lista bejárását mindkét irányban, amiért cserébe azonban némileg megnövekedett tárigénnyel, bonyolultabb listakezelő kóddal és potenciálisan inkonzisztens listaszerkezettel kell fizetnünk. A listában inkonzisztencia a hivatkozások sérülésekor vagy hibás listakezelő algoritmusok alkalmazása esetén állhat elő, és azt eredményezheti, hogy a listát a két különböző irányban bejárva különböző számú és/vagy eltérő elemeket találunk benne.

Ciklikusan láncolt listák[szerkesztés]

A ciklikusan láncoltak azok a listák, amelyek kvázi nem rendelkeznek első és utolsó elemmel, mert a lista úgymond "utolsó" eleme az úgymond "első" elemet jelöli meg következő elemként, illetve dupla láncolás esetében ugyanígy igaz az előző elem vonatkozásában is. Ciklikusan láncolt listát abban az esetben szokás alkalmazni, ahol nem számít az, hogy a listán belül milyen pozíción helyezkedik el egy adott elem, mert a lista folyamatosan bejárásra kerül, a kvázi utolsó elem után ismét az első elemre sort kerítve. A ciklikusan láncolt listák esetében pontosan ezért rendkívüli körültekintéssel kell a feldolgozó eljárásokat lekódolni a végtelen ciklusok elkerülése végett.

A ciklikusan láncolt lista előnye, hogy tetszőleges elemére mutató hivatkozás birtokában a lista teljes egésze garantáltan bejárható. (Egyszerű lista esetében az első elemre mutatkozó hivatkozás szükséges a garantáltan teljes bejáráshoz.)