A láncolt lista (angolul linked list) egyike a számítógép-programozásban használatos legegyszerűbb adatszerkezeteknek. Olyan csomópontok, cellák sorozatából épül fel, amelyek tetszőleges számú és típusú adatmezőt, és egy vagy két hivatkozást tárolnak. A hivatkozás(ok) a lista következő (és előző) elemére mutat(nak). A láncolt szerkezet lehetővé teszi listaelemek törlését és beszúrását a lista tetszőleges pontjára konstans (azaz a konkrét helytől független) időben, ugyanakkor egy véletlenszerűen kiválasztott elem előkeresése a lista hosszával arányos időt igényel.
Változatok Egyszeresen láncolt lista
A láncolt lista legegyszerűbb formája az egyszeresen láncolt lista, amelyben cellánként egy hivatkozás található. Ez a hivatkozás a lista következő elemére mutat, speciálisan az utolsó elem esetén nullértékű vagy egy kitüntetett üres listára hivatkozik.
bélyegkép|középre|408px|Egy három elemből álló egyszeresen láncolt lista. Minden elem két mezőt tartalmaz: egy adatot (itt a példában egy egész számot), és egy hivatkozást a következő elemre. Az utolsó elem hivatkozása a lezárásra mutat.
Ha egy egyszeresen láncolt listára akarunk hivatkozni (például paraméterátadáskor), elegendő megadnunk az első elemének címét.
Kétszeresen láncolt lista
Valamivel elmésebb adatszerkezet a kétszeresen láncolt lista. Itt minden cellában két hivatkozást tárolunk, az egyik a lista előző, a másik a következő cellájára mutat.
bélyegkép|középre|610px|Kétszeresen láncolt lista három elemmel. Minden elem három mezőt tartalmaz: egy adatot (itt a példában egy egész számot), egy hivatkozást az előző elemre és egy hivatkozást a következő elemre. Az első elem előre mutató hivatkozása a kezdésre, az utolsó elem hátra mutató hivatkozása a lezárásra mutat.
Körkörös lista
Egy körkörös listában az első és az utolsó elem össze van kötve egymással. Ez a megoldás működik mind egyszeresen, mint kétszeresen láncolt szerkezeteknél. Egy körkörös lista bejárását természetesen tetszőleges eleménél elkezdhetjük, a körbeérés felismeréséhez csupán azt kell megjegyeznünk, hogy ezt pontosan melyik elemnél tesszük.
bélyegkép|középre|350px|Példa a körkörös listára
Őrcellák
Láncolt listák esetén gyakori trükk a valódi adatot nem tároló, ún őrcellák használata a lista elejének vagy végének jelzéséhez. Ennek célja bizonyos műveletek megkönnyítése vagy felgyorsítása, ekkor ugyanis a programozó élhet azzal a feltételezéssel, hogy a lista minden (valós) elemének van rákövetkező (vagy megelőző) eleme, valamint hogy minden listának van legalább egy (hamis) legelső és egy legutolsó eleme. Elterjedt magyar szó a lista elején lévő őrcellára a fejelem.
Alkalmazása
A láncolt listákat gyakran alkalmazzák összetettebb adatstruktúrák, mint például verem vagy sor építésekor.
A cellák adatmezői tetszőleges adatot tárolhatnak, így akár hivatkozást is egy másik láncolt listára. Ezzel a trükkel már nem csak lineáris adatszerkezeteket tudunk építeni, hanem tetszőleges elágazó struktúrát, mint például fákat, gráfokat stb. Ez az ötlet a Lisp programozási nyelvből származik, amelyben a láncolt lista a legalapvetőbb adatstruktúra, de mára számos más programozási nyelv fontos eszközévé vált.
Láncolt listákkal időnként asszociatív tömböket is megvalósítanak, ebben az értelemben gyakran asszociatív listaként hivatkoznak rájuk. Ezen felhasználás hatékonysága azonban erősen megkérdőjelezhető, mivel már kis adatmennyiség esetén is jelentősen elmarad más adatszerkezetek, mint például a kiegyensúlyozott bináris keresőfa hasonszőrű alkalmazásától. A két adatstruktúra kombinálása (bináris fa, ahol az elemek egyúttal rendezett láncolt listába is vannak fűzve) ugyanakkor gyakran hasznos lehet.
Előnyök és hátrányok
Ahogy az általában igaz a számítógép-programozásban és a programtervezésben, egyetlen adatstruktúra, így a láncolt lista sem egyformán alkalmas minden esetben. Ez a szakasz a láncolt lista különböző alkalmazásainak előnyeit és nehézségeit mutatja be. Általánosan igaz, hogy ha folyamatosan változó összetételű és méretű adatstruktúrára van szükségünk, elemek rendszeres hozzáadásával és törlésével, a láncolt lista többnyire jó döntés. Ha azonban ritkán akarunk az adatokon változtatni, viszont fontos az elemek konstans-idejű elérése, feltehetően nem a láncolt lista a legjobb megoldás.
Láncolt listák és tömbök összevetése
A láncolt lista számos előnnyel rendelkezik a hagyományos tömbhöz képest. Egy lista tetszőleges helyére könnyen beszúrhatunk új elemeket, vagy tetszőleges helyről törölhetünk, a lista hosszától független időigényű műveletekkel (feltéve, hogy a hely ismert). Tömb esetén ezek a műveletek az elemek számával arányos ideig tartanak, mivel művelet helye mögött álló elemeket mozgatni kell (beszúrás esetén hátrafelé, törlés esetén előre). Míg egy láncolt lista méretének csak a fizikai memória mérete szab határt, addig egy tömb méretét előre meg kell határozni, és lehetőség szerint menet közben, igény szerint növelni vagy csökkenteni kell, ez azonban a teljes tömb lemásolását igényli minden egyes átméretezésnél. Amennyiben a tárolni kívánt listák farok-részei között nagy átfedések vannak, a láncolt lista további memóriamegtakarítást tesz lehetővé ezen szakaszok megosztásával.
Ugyanakkor a tömb lehetővé teszi az elemek véletlen elérését, míg egy láncolt listában ez csak rögzített sorrendben lehetséges. Éppen ezért a láncolt lista nem alkalmas olyankor, amikor a lista elemeire nem sorrendben van szükség. Tömbök sorrendi bejárásánál a legtöbb hardver architektúra esetén hasznot húzunk a beépített gyorsítótár működéséből is, láncolt listák esetén (ahol az elemek memóriabeli elhelyezkedése nem szekvenciális) ez az előnyünk sincs meg. Ezen túl a tömbök egy elemre eső memóriaigénye kisebb, mint a láncolt listáé, mivel nem kell a láncoló mutatót vagy mutatókat eltárolnunk. Ez különbség különösen kis méretű adatmezőknél (karaktereknél, logikai értékeknél) érezhető. Natív megvalósítás esetén, ha a láncolt lista celláit egyesével foglaljuk le, lényeges különbség lehet futási időben is, főként a lista kezdeti feltöltésekor.
Ezen problémák enyhítésére számos láncolt lista variánst terveztek. Egyes megoldások például több mint egy adatot tárolnak egyetlen cellában, növelve a gyorsítótár hatékonyságát, csökkentve a láncoló mutatókból adódó pluszköltséget.
Egyszeres vagy kétszeres láncolás? Kétszeres láncolás esetén nagyobb a lista plusz memóriaigénye, és drágábbak az elemi műveletek is. Ugyanakkor könnyebb az adatok manipulálása és keresése. Különösen figyelemre méltó a különbség listaelem törlésénél, amely (ha kezdetben csak a törlendő elemet ismerjük) egyszeres láncolás esetén a listaelemek számával arányos időigényű (hiszen meg kell keresnünk a megelőző elemet), kétszeres láncolás esetén viszont konstans. Szintén hátrány, hogy kétszeres láncolásnál a közös szakaszok nem oszthatók meg.
Körkörös listák A körkörös listák leginkább eleve körkörös szerkezetek leírására alkalmasak, előnyük, hogy bejárásukat bármelyik elemnél elkezdhetjük. Hátrányuk, hogy a végjelek hiánya miatt különös körültekintést igényel egy bejárás végének felismerése.
Őrcellák Őrcellák bevezetésével biztosíthatjuk, hogy minden (valódi) elemnek van rákövetkező vagy megelőző eleme, és így számos műveletnél megspórolhatjuk a különleges esetek kezelését. Az árnyoldaluk, hogy megnövelik a lista memóriaigényét (bár ez csak sok rövid lista esetén lehet probléma).
Műveletek
Ebben a szakaszban a listákon végezhető legalapvetőbb műveleteket (bejárás, elem beszúrása, törlése) tekintjük át a különféle változatok esetében. A programrészletek pszeudokódban íródtak. A lista végjelére végig null-ként fogunk hivatkozni, ez azonban sokféleképpen megvalósítható.
Egyszeresen láncolt listák műveletei
Egy egyszeresen láncolt lista cellájának két mezője van, ezt a Node adatszerkezettel adjuk meg. Emellett nyilvántartunk egy head változót is, amely mindig a lista első cellájára mutat, vagy null értékű, ha a lista üres.
struct Node data // A cellában tárolt adat, gyakran csak egy hivatkozás a tényleges adatra Node next // Hivatkozás a következő cellára
declare head as Node // A lista legelső cellája
Egy lista bejárása meglehetősen egyszerű:
node = head // A lista fejénél kezdjük... while node ≠ null // …és addig megyünk, amíg végig nem érünk (valamilyen művelet a node.data mezőn) node = node.next // továbblépünk a következő mezőre
A következő kódrészlet beszúr egy elemet egy adott cella után. (Egyszeresen láncolt listával cellák elé nem lehet elemeket fűzni, ehhez valamilyen módon meg kell találni a megelőző elem celláját.)
function insertAfter(Node node, Node newNode) // newNode beszúrása node után newNode.next = node.next // newNode rákövetkező cellája node eddigi rákövetkező cellája lesz node.next = newNode // node rákövetkező cellája mostantól newNode
Ahhoz, hogy a lista elejére fűzzünk be egy elemet, külön függvényre van szükség, amely módosítja a head változót:
function insertBeginning(Node newNode) // newNode beszúrása a lista elejére newNode.next = head // newNode után következik a teljes eddigi lista head = newNode // newNode a lista új feje
A beszúráshoz hasonlóan két függvényünk van elemek törléséhez is: az egyik egy adott cella utáni elemet törli, a másik a lista fejét. (Az első működése definiálatlan, ha a lista utolsó elemére hívjuk meg, a másodiké pedig akkor, ha a lista üres, azaz head = null.)
bélyegkép|középre|380px|Elem törlése egy egyszeresen láncolt listából
function removeAfter(Node node) // a node után következő cella törlése nodeBeingRemoved = node.next // ezt a cellát akarjuk törölni node.next = node.next.next // node rákövetkező eleme mostantól az eddig kettővel utána álló lesz destroy nodeBeingRemoved // a törölt cella memóriaterületének felszabadítása
function removeBeginning(Node node) // a lista fejének törlése nodeBeingRemoved = head // ezt a cellát akarjuk törölni head = head.next // a lista feje mostandól az eddigi második elem lesz destroy nodeBeingRemoved // a törölt cella memóriaterületének felszabadítása
Kétszeresen láncolt listák műveletei
Kétszeresen láncolt listák esetén több munkát igényel a hivatkozások gondozása, de kevesebb információ is elég egy cella megtalálásához. Egy cella törléséhez például nem szükséges külön nyilvántartanunk az őt megelőző elemet, mivel ez az információ nyilván van tartva magában a cellában. A bonyolultabb szerkezetnek megfelelően kibővítjük a node struktúrát egy prev mutatóval, és felveszünk egy tail változót, amely mindig a lista legutolsó elemére hivatkozik. Üres lista esetén, mind a head, mind a tail változók nullértékek.
Egy kétszeresen láncolt lista mindkét irányból bejárható, szükség esetén akár menet közben is lehet irányt váltani.
Bejárás előre node = head // A lista első eleménél kezdjük a bejárást while node ≠ null // Addig megyünk, amíg el nem érjük a lista végét (művelet a node.data mezőn) node = node.next // Továbblépünk a következő mezőre
Bejárás hátrafelé node = tail // A lista utolsó eleménél kezdjük a bejárást while node ≠ null // Addig megyünk, amíg el nem érjük a lista elejét (művelet a node.data mezőn) node = node.prev // Továbblépünk az előző mezőre
Az alábbi két függvény egy cella elé, ill. után fűz be egy új elemet:
function insertAfter(Node node, Node newNode) // newNode befűzése node után newNode.prev = node // newNode megelőző eleme node lesz newNode.next = node.next // newNode rákövetkező eleme node eddigi rákövetkező eleme if node.next = null // Ha a lista végére szúrtunk be… tail = newNode // ...akkor módosítsuk az utolsó elemre mutató változót, ... else // …különben… node.next.prev = newNode // ...a következő elem megelőző eleme newNode legyen node.next = newNode // node rákövetkező eleme newNode lesz
function insertBefore(Node node, Node newNode) // newNode befűzése node elé newNode.next = node // newNode következő eleme node lesz