Láncolt lista

A láncolt lista 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 fajtájú 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.

Egy három egész elemből álló egyszeresen láncolt lista

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.

Kétszeresen láncolt lista

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.

Ő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.

Láncolt listák 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épprogramozá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.)

 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
     newNode.prev = node.prev     // newNode megelőző eleme node eddigi megelőző eleme
     if node.prev = null          // Ha a lista elejére szúrtunk be…
         head = newNode           // …akkor módosítsuk az első elemre mutató változót, …
     else                         // …különben…
         node.prev.next = newNode // …az előző elem rákövetkező eleme newNode legyen
     node.prev = newNode          // node megelőző eleme newNode lesz

Szükségünk van egy külön függvényre ahhoz, hogy megkezdjünk egy üres listát:

 function insertBeginning(Node newNode) // newNode beszúrása a lista elejére
     if head = null                  // Ha a lista üres..
         head = newNode              // …akkor mostantól álljon ebből az egy elemből, …
         tail = newNode
         newNode.prev = null
         newNode.next = null
     else                            // …különben…
         insertBefore(head, newNode) // …szúrjuk be az elemet hagyományos módon.

Ennek párja az a függvény, ami a lista végére fűz be egy elemet:

 function insertEnd(Node newNode) // newNode beszúrása a lista végére
     if tail = null                 // Ha a lista üres…
         insertBeginning(newNode)   // …akkor a lista eleje és vége megegyezik, …
     else                           // …különben…
         insertAfter(tail, newNode) // …szúrjuk be az elemet hagyományos módon.

Egy csomópont törlése sokkal egyszerűbb a kétszeres láncolásnak köszönhetően:

 function remove(Node node) // node törlése a listából
     if node.prev = null            // Ha node a lista feje volt eddig…
         head = node.next           // …akkor a fej mostantól a következő elem, …
     else                           // …különben…
         node.prev.next = node.next // …az előző elem rákövetkező eleme legyen node rákövetkező eleme

     if node.next = null            // Ha node a lista utolsó eleme volt eddig…
         tail = node.prev           // …akkor az utolsó mostantól a megelőző elem, …
     else                           // …különben…
         node.next.prev = node.prev // …a következő elem megelőző eleme legyen node megelőző eleme
     destroy node                   // A node által lefoglalt memóriaterület felszabadítása

Ezen függvény egyik kellemes tulajdonsága, hogy egy egyelemű lista egyetlen elemének törlésekor a head és tail mutatók automatikusan null értéket kapnak.

Körkörös listák műveletei

Egy körkörös lista lehet egyszeresen vagy kétszeresen láncolt, a lényeg, hogy körkörös listát kapunk, ha egy egyenes listában az első és az utolsó elemet a szabad végüknél összekötjük. Előnye, hogy nem szükséges a lista fejét nyilvántartanunk (mivel ilyen elem nem is létezik), elegendő egy tetszőleges elemére hivatkozó mutató. Legyen ez a következő példákban someNode.

Bejárás előre

 node := someNode // A lista ismert eleménél kezdjük a bejárást
 do
     (művelet node.value adatmezőn)
     node := node.next // továbblépés a következő elemre
 while node ≠ someNode // ciklus amíg körbe nem értünk

Bejárás hátrafelé (kétszeres láncolás esetén)

 node := someNode // A lista ismert eleménél kezdjük a bejárást
 do
     (művelet node.value adatmezőn)
     node := node.prev // továbblépés az előző elemre
 while node ≠ someNode // ciklus amíg körbe nem értünk

Vegyük észre, hogy ezúttal hátultesztelő ciklust használtunk.

Az alábbi függvény egy kétszeresen láncolt, körkörös listába fűz egy elemet:

 function insertAfter(Node node, Node newNode) // newNode befűzése node után
     newNode.next := node.next // newNode rákövetkező eleme node eddigi következő eleme
     newNode.prev := node      // newNode megelőző eleme node
     node.next.prev := newNode // node eddigi rákövetkező elemének megelőző eleme mostantól newNode
     node.next      := newNode // node rákövetkező eleme newNode

Egy elem beszúrása egy esetlegesen üres listába külön körültekintést igényel:

 function insertBeginning(Node node) // node beszúrása körkörös listába
     if someNode = null                   // ha a lista eddig üres volt…
         node.prev := node                // akkor mostantól csak a node elemből áll
         node.next := node
     else                                 // …különben…
         insertAfter(someNode.prev, node) // a már meglévő listába szúrjuk be az új elemet
     someNode := node                     // az ismert elem az új elem legyen

Elem törlésekor pedig a lista kiürülésére kell figyelni:

 function remove(Node node) // node törlése a listából
     if node.next = node             // ha ez az egyetlen elem…
         someNode := null            // akkor a lista üres lesz
     else                            // …különben…
         node.next.prev := node.prev // a törlendő elemet kifűzzük a listából
         node.prev.next := node.next
     destroy node                    // végül felszabadítjuk a lefoglalt memóriát

Láncolt listák megvalósítása cellák tömbjével

Vannak nyelvek, amelyek nem támogatják mutatók használtatát. Ilyenkor a hivatkozásokat helyettesíthetjük egy tömb indexeivel. A megközelítés lényege, hogy minden cellát egy tömb egy-egy rekordjával (sorával) írunk le. A láncolást a cellákban mutatók helyett más sorokra hivatkozó indexekkel oldjuk meg. A tömbnek nem feltétlenül használjuk az összes sorát, sőt, az aktuálisan használt sorok még csak nem is feltétlenül folytonosak, mivel törléskor könnyen keletkezhet lyuk. Ha az adott nyelvben rekordokat sem lehet létrehozni, akkor több azonos méretű tömbre van szükség (mezőnként egyre).

Példaként tekintsük az alábbi, Visual Basic-ben definiált adatstruktúrát:

TYPE listrec
    Next as Integer
    Prev as Integer  ' ha kétszeresen láncolt listát szeretnénk
    Name as String
    Balance as Float
END TYPE

Ebből a struktúrából tömböt építve létre tudunk hozni láncolt listákat. A lista fejének megtalálásához külön el kell tárolnunk annak indexét:

Dim ListHead as Integer
Dim LinkedList(1000) as listrec

A hivatkozások, mint az már szerepelt, egyszerűen a hivatkozott rekordok indexei, mint az az alábbi példán is látható:

Index	Next	Prev	Name	Balance
0	1	4	Jones, John	123.45
1	-1	0	Smith, Joseph	234.56
2	4	-1	Adams, Adam	0.00
3			Ignore, Ignatius	999.99
4	0	2	Another, Anita	876.54
5
6
7

Ebben a példában a ListHead változó értéke 2, mivel a lista feje a második sorban van eltárolva. Vegyük észre, hogy a 3. és 5-7. sorok nem részei a listának, ezért felhasználhatjuk őket új elemek hozzáadásakor. Egy újabb ListFree változó bevezetésével a szabad sorokat is beláncolhatjuk egy külön listába, és így (ezt a listát is megfelelően karbantartva) bármikor gyorsan tudunk találni szabad rekordokat. Természetesen ha már minden rekordot használunk, új elemet csak a tömb megnövelésével tudunk felvenni.

Mik ennek a módszernek az előnyei?

• A teljes lista könnyen mozgatható a memóriában, nem kell mást tenni, mint a teljes tömböt lemásolni (egyetlen másolási művelettel). Hasonlóképpen könnyen írható ki külső adattárolóra, vagy olvasható vissza onnan, a lista bejárása nélkül.
• Egy egész változóban tárolt sorindex gyakran kevesebb memóriát foglal, mint egy mutató.
• Mivel a tömb elemei a memóriában egymás közelében helyezkednek el, a gyorsítótár ki tudja fejteni a hatását.

A módszer hátránya, hogy a lista mérete messze nem kezelhető annyira rugalmasan, mint klasszikus láncolt listák esetében. A hossznövelés költsége ráadásul egyenesen arányos a lista hosszával, mivel a tömb minden egyes átméretezésekor le kell másolni az összes adatot. Az átméretezés azért is problémás lehet, mert nem mindig könnyű találni egy nagy, összefüggő, szabad memóriaterületet, klasszikus megvalósítás esetén viszont mindig csak egy-egy cella számára szükséges memóriát kell lefoglalni.

Nyelvi támogatás

Számos programozási nyelv, mint például a Lisp vagy a Prolog nyelvi szinten támogatja a láncolt listákat. Más nyelvek esetében magunknak kell felépíteni ezeket az adatstruktúrákat hivatkozások és rekordok használatával. Következzék egy C nyelvű megvalósítás:

#include <stdlib.h>  /* for malloc */
#include <stdio.h>   /* for formatted input-output*/

typedef struct ns {
	int data;
	struct ns *next;
} node;

node *list_add(node ** p, int i) {
    node *n = (node *) malloc(sizeof(node));
    n->next = *p;
    *p = n;
    n->data = i;
    return n;
}

void list_remove(node ** p) {
    if (p) {
        node *n = *p;
	*p = (*p)->next;
	free(n);
    }
}

node **list_search(node ** n, int i) {
    if (!n) return NULL;
    while (*n) {
        if ((*n)->data == i) {
            return n;
        }
    n = &(*n)->next;
    }
    return NULL;
}

void list_print(node * n) {
    if (!n) printf("list is empty\n");
    while (n) {
        printf("print %p %p %i \n", n, n->next, n->data);
        n = n->next;
    }
}

int main() {
    node *n = NULL;

    list_add(&n, 0);
    list_add(&n, 1);
    list_add(&n, 2);
    list_add(&n, 3);
    list_add(&n, 4);
    list_print(n);
    list_remove(&n);            /* remove head */
    list_remove(&n->next);      /* remove second */
    list_remove(list_search(&n, 1));
    list_remove(&n->next);      /* remove tail */
    list_remove(&n);            /* remove last */
    list_print(n);

    return 0;
}

Kapcsolódó adatszerkezetek

Az ugró lista olyan láncolt lista, amelyben további mutatók segítségével igény szerint kisebb-nagyobb ugrásokat tehetünk bejáráskor. Lehetnek például mutatók, amelyek a következő 4, 16, 64 stb. elemet ugorják át. Ezek használatával nagyon gyorsan eljutjatunk egy elemhez, ha pontosan ismerjük a helyét.

Egy bináris fa nagyon hasonló szerkezetű egy láncolt listához, csak ott egy következő elem helyett minden elemnek (legfeljebb) két "következő" eleme lehet.

További információk

A Stanford Egyetem Számítástudományi Tanszékének oktatási anyaga:

• Bevezetés a láncolt listákhoz
• Feladatok láncolt listákkal