Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

3.2. A láncolt lista (mutatós és tömbös implementáció)

3.2. A láncolt lista (mutatós és tömbös implementáció)

Egy másik lehetőség a sorozat implementálására a láncolt lista.

3.3. Definíció. A láncolt lista adatstruktúra

A láncolt lista (linked list) olyan dinamikus halmaz, melyben az objektumok, elemek lineáris sorrendben követik egymást. A lista minden eleme mutatót tartalmaz a következő elemre. Műveletei: keresés, beszúrás, törlés.

A láncolt listáról nem feltételezzük, hogy az egymást követő elemei a memóriában valamilyen szabályszerűségnek megfelelően követik egymást. Az elemek lehetnek bárhol, az egyes elemeket mutatón keresztül érhetjük el, nem az index révén.. Ha valamely elemet – például az elsőt - megtaláltuk, akkor a rákövetkezőt is megtaláljuk a benne lévő mutató alapján. Az elem számára helyet foglalni elegendő csak a keletkezése pillanatában. Megszünésekor helyét felszabadíthatjuk. Ennek feltétele, hogy elérhető legyen a dinamikus memória gazdálkodás. A láncolt listák a mutatók és a kulcsok alapján osztályozhatók az alábbi egymást ki nem záró szempontok szerint.

Az listának, mint struktúrának az attributuma a fej[L], ami egy a lista első elemére mutató mutató. Ha fej[L] = NIL, akkor a lista üres. A listaelemek attributumai az alábbi táblázatban következnek. A tárgyalásban kétszeresen láncolt, nem rendezett, nem ciklikus listáról van szó. A listaelemet az mutató révén érhetjük el.

Tekintsük át most a műveletek pszeudokódjait. Elsőként a keresés. A keresésnél a listafej információ alapján a lista kezdetét megtaláljuk és a köv mutatók révén végig tudunk lépkedni a listaelemeken, miközben vizsgáljuk a kulcsok egyezőségét. A legrosszabb eset az, amikor az elem nincs a listában. Ilyenkor minden elem vizsgálata sorrakerül és ez adja a lineáris időt.

A beszúrást konstans idő alatt azáltal tudjuk elvégezni, hogy az új elemet mindig a lista legelső eleme elé szúrjuk be. Ekkor mindegy, hogy hány elem van a listában, a beszúrási idő ugyanannyi.

Szintén megoldható konstans idő alatt a beszúrás a lista tetszőleges eleme elé, vagy mögé, amennyiben az elemre mutató mutató meg van adva. Ha a mutató helyett az elem kulcsa van megadva, akkor lineáris idejű a beszúrás, mivel a beszúrás tényleges elvégzése előtt az elemet meg kell keresni a listában.

Törlésnél az elem nem szűnik meg létezni, csak a listából kiláncolódik, a listán lépkedve többé nem érhető el. Elérhető viszont más úton akkor, ha valahol maradt valamilyen mutató, amely rá mutat. A konstans idő abból adódik, hogy az algoritmus input adataként a törlendő elem mutatóját adjuk meg, így az elemet nem kell keresni. Ha az inputban a törlendő elem kulcsa szerepelne, akkor a kiláncolás előtt előbb a kulcs alapján az elemet meg kellene keresni, ami miatt az idő lineárissá nőne.

Némi kényelmetlenséget jelent a lista kezelésénél a listavégek állandó vizsgálata, valamint hogy a végeken az algoritmus lépései eltérnek a középen alkalmazott lépésektől. Ennek a feloldása úgynevezett szentinel (őrszem, strázsa) alkalmazásával megoldható.

Legyen nil[L] egy mutató, amely az alábbi szerkezetű elemre mutat:

Ez az elem testesíti meg a nem létező NIL elemet. Ezzel az elemmel tulajdonképpen egy ciklikus listát valósítunk meg, melyben egy olyan kulcsú elem van, amelyről azonnal eldönthető, hogy a valódi listához nem tartozhat hozzá. Bármilyen irányban haladunk a listán, mindig jelezni tudjuk a kulcs vizsgálata révén, hogy a lista elejére, vagy a végére értünk. Ennek a listának a sajátossága, hogy köv[nil[L]] a lista első elemére mutat, elő[{nil}[L]] pedig az utolsó elemére. A lista utolsó eleme esetében köv[x] = nil[L], az első eleme esetében pedig elő[x] = nil[L]. A fej[L] attributumra nincs szükség!

Ennek megfelelően az algoritmusaink az alábbi módon változnak, egyszerűsödnek.

A rendezett lista rendezettségi tulajdonságait sajnos nem tudjuk kihasználni algoritmus gyorsításra. Ha a dinamikus memória gazdálkodás nem elérhető, vagy nem kívánunk vele élni, vagy egyszerűen nem vonzódunk a mutatók használatához (bár ez utóbbi nem úri passzió kérdése egy informatikai rendszer kifejlesztésekor), akkor a láncolt lista adatstruktúra realizálható, implementálható tömbbel is. Ekkor minden tömbelemet kiegészítünk ,,mutató” mezőkkel, amelyek valójában tömbelem indexeket fognak tárolni. A listafej is egy különálló, egész számot tároló rekesz lesz, amely megmutatja, hogy a tömb melyik eleme számít a lista kezdő elemének. A műveletek realizálásának pszeudokódjában a beszúrásnál most azt is figyelni kell, hogy van-e még fel nem használt rekesz a tömbben, vagyis, hogy a rendelkezésre álló memória korlátos. Természetesen a valódi mutatók használatakor is figyelni kell a memóriát, hiszen minden új elem megjelenése új memóriaigényt támaszt. A tömbös realizációhoz javasolható a következő séma. Legyen a fej annak a rekesznek a neve, melyben a lista első elemének a tömbelem indexe található. A NIL mutatót szimbolizálja a zérus. A listaelemek tárolására rendelkezésre bocsátott tömb neve legyen A, elemeinek indexelése induljon 1-től és tartson max n-ig. Minden tömbelem, mint rekord álljon a kulcsmezőből, az információs mezőkből, valamint a ,,mutató” mezőkből (előző elemre és a következő elemre mutatók). A zérus realizálja itt is a NIL mutatót.

3.1. Példa. Álljon a listánk a következő kulcsú elemekből: 423, 356, 764, 123, 987, 276, 839. Tömbös realizácóval a következőképpen nézhet ki egy ilyen láncolt lista egy tömbben, amelynek mondjuk 10 eleme van. A rekordokból (sorokból) az információs mezőket kihagyjuk, mert a tárgyalás szempontjából lényegtelenek

Ha most a fenti listába be kellene szúrni a 247-es kulcsot, akkor ez többféle módon is megtehető. Be lehet szúrni - ha semmilyen megkötés sincs – az új elemet a lista elejére az első elem elé. Másik lehetőség, hogy megmondják, hogy például szúrjuk be a 356-os kulcsú elem mögé. Van ezeken kívül még sok lehetőség. Nézzük az említett két esetet. Az új elemet egyelőre helyezzük el mondjuk a tömb 2-es indexű helyén, ami jelenleg üres és a listához nem tartozik hozzá. A lista első eleme az új elem lesz, tehát az ő elő mutatója zérus lesz, és a régi első elem elő mutatója az új elemre fog mutatni, tehát 2-re változik. Meg kell még adni az új első elem köv mutatóját, amely a régi első elemre mutat, tehát értéke 3 lesz, ami korábban a fej mutató volt. A fej mutatónak pedig az új első elemre kell mutatni, tehát értéke 2 lesz. Látható, hogy a művelethez a mutatókat illetően négynek a megváltoztatására volt szükség. Ezek után az új lista tömbös megjelenése alább látható a baloldali táblázatban. A változásokat vastagítva és aláhúzva jelenítettük meg. A másik esetben az új elem elő mutatója a 356-osra fog mutatni, amely a 6-os helyen van, a köv mutatója pedig a 356-os köv mutatóját kapja, vagyis 1-et. A 356-os köv mutatója is és a 356 mögött korábban álló elem (a 764-es kulcsú) elő mutatója is az új elemre mutat, tehát mindkettő értéke 2. Vigyázni kell a mutatók megváltoztatásánál. A 764-es elő mutatóját hamarabb kell megváltoztatni, mint a 356-os köv mutatóját, mert ellenkező esetben a 356-os köv mutatója már nem a 764-esre mutat. Itt is négy mutató változott. Az eredmény az alábbi jobboldali táblázatban látható.

3.2. Példa. Az 1. példabeli listából töröljük a 356-os kulcsú elemet. A kulcs alapján először az elemet meg kell keresni, hogy ismerjük a helyét (a tömbelem indexet). A fej-töl elindulva az első elem a 3-as indexű, az ő kulcsa 423, ami nem jó nekünk. A 3-as köv mutatója 6, és a 6-os indexű kulcsa 356, amit kerestünk. Tehát a listából a 6-os indexűt kell törölni, ami a lista láncából történő kiláncolást jelenti, tehát maga az elem nem semmisül meg. A kiláncoláshoz megnézzük, hogy melyik a megelőző elem. Ez az elő mutató szerint a 3-as. Ezért a 3-as köv mutatóját lecseréljük a 6-os köv mutatójára, azaz 1-re, és a 6-os köv mutatója szerinti 1-es indexű elem elő mutatóját lecseréljük a 6-os elő mutatójára, azaz 3-ra. A törléshez tehát elegendő volt két mutatót megváltoztatni. Az eredmény az alábbi táblázatban látható: