Láncolt lista
| Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
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 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
szerkesztésEgyszeresen láncolt lista
szerkesztésA 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.
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
szerkesztésValamivel 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örkörös lista
szerkesztésEgy 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
szerkesztésLá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
szerkesztésA 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
szerkesztésAhogy 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
szerkesztésA 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?
szerkesztésKé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
szerkesztésA 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
szerkesztésŐ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
szerkesztésEbben 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
szerkesztésEgy 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
szerkesztésKé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
szerkesztésEgy 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
szerkesztésVannak 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
szerkesztésSzá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;
}
Belső és külső tárak
szerkesztésKapcsolódó adatszerkezetek
szerkesztésAz 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.
Jegyzetek
szerkesztésForrások
szerkesztésTovábbi információk
szerkesztésA Stanford Egyetem Számítástudományi Tanszékének oktatási anyaga:
