7.3. Láncolt lista

Míg a tömbök esetén a tömbindexek határozzák meg a lineáris sorrendet, a listákban ezt a mutatókkal érjük el. Listák esetén a lista fejének, azaz első elemének megadására van szükségünk. Az L lista fejét L.fej-jel jelöljük. Egyszerűbb esetben minden rekord (összefüggő adatok csoportja) tartalmaz egy mutatót a soron következő rekordra, ezt egyszeresen láncolt listának nevezzük.

7.1. ábra - Egyszeresen láncolt lista

Egyszeresen láncolt lista


Ha minden rekord tartalmaz egy mutatót az őt megelőző rekordra is, akkor kétszeresen láncolt listáról beszélünk.

7.2. ábra - Kétszeresen láncolt lista

Kétszeresen láncolt lista

Az x elemet követő illetve az x elemet megelőző elemre x.köv és x.előző jelöléssel hivatkozunk. Ha a lista első és utolsó elemét összekapcsoljuk, ciklikus listát kapunk.

7.3. ábra - Kétszeresen láncolt, ciklikus lista

Kétszeresen láncolt, ciklikus lista

Ha a soron következő elemek nagyság szerint növekszenek, akkor rendezett listáról beszélhetünk. A következőkben nem rendezett, kétszeresen láncolt rekordokkal foglalkozunk. A veremtől és sortól eltérően a láncolt listák esetén a többi lekérdező műveletet is használhatjuk. Itt most csupán a keresést mutatjuk be. Ha n hosszú listában keresünk, akkor lehet, hogy minden elemet meg kell vizsgálnunk, tehát a keresés bonyolultsága lineáris, azaz O(n). A listafejbe szúrás konstans, azaz O(1) bonyolultságú, mivel csupán mutató-átállításra van szükség.

7.4. ábra - Listafejbe szúrás

Listafejbe szúrás


Ha a törlésnél ismerjük a törlendő elem címét, akkor a törlés konstans, azaz O(1) bonyolultságú. Ha csak a törlendő elem kulcsát ismerjük, akkor végre kell hajtani a LISTÁBAN-KERES eljárást törlés előtt, s így az együttes bonyolultság lineáris.

7.5. ábra - Listából törlés

Listából törlés


Function LISTÁBAN-KERES(L,k) 
Input: L lista, k keresett kulcs 
Output: A keresett elem címe, illetve Nil 
1 x = L.fej 
2 while x != Nil and x.kulcs != k do 
3    x = x.köv
4 endw 
5 return x 

Procedure LISTÁBA-SZÚR(L,x) 
Input: L lista, x beszúrandó elem 
Eredmény: Az új lista feje az x elem, a farka a régi lista 
1 x.köv = L.fej 
2 if L.fej != Nil then 
3    L.fej.előző = x 
4 endif
5 L.fej = x 
6 x.előző = Nil 

Procedure LISTÁBÓL-TÖRÖL(L,x) 
Input: L lista, x törlendő listaelem címe 
Eredmény: A listából törli a megadott elemet 
1 if x.előző != Nil then 
2    x.előző.köv = x.köv 
3 else 
4    L.fej = x.köv
5 endif 
6 if x.köv != Nil then 
7    x.köv.előző = x.előző 
8 endif