Gyakorlati alapok III.

Az adatszerkezetek - Lista

Ahhoz, hogy egy adatszerkezetben megtaláljunk egy elemet:

• vagy címezhető helyen kell lennie,

• vagy léteznie kell egy sornak, amelyen végig tudok menni.

Ha tehát nem címezzük meg egy adott elem helyét, akkor csak úgy tudjuk tárolni, ha fizikailag egymás után sorba rakjuk őket. Ebben az adattárolási szerkezetben az adatok konkrét címeket tartalmazó mutatókon keresztül vannak összekapcsolva, ezáltal mintegy "láncolva":

Forrás - Source: Gábor Dénes Főiskola

Adott egy kezdő elem: egy mutató, pointer (L), amelyik Adat1-re mutat. Az első elemet egy újabb mutató követi (L2), amely Adat2-re mutat és így tovább. Az adatszerkezet ilyen módon mutatókon keresztül szekvenciálisan járható be, bár elejére és végére is új elemek kapcsolhatók. Ha egy mutató nem mutat sehova, akkor vége a láncnak, de a véget általában 1 egyértelműen azonosítható végjel jelzi.

A fenti példában egy láncolt listát látunk. A láncot tehát az elemek közötti mutatók biztosítják. Láncolt lista esetében az elemek fizikailag lehetnek más sorrendben vagy egészen máshol, ám a mutatók biztosítani fogják a számunkra kívánt rendezettséget. Ebből következik, hogy a tömbbel ellentétben egy láncolt listából könnyebb törölni, mivel csak át kell állítanunk a mutatót a törölt elemről a törölt elem utáni elemre, tömbelem törlése esetén azonban az elemhely ott marad üresen. Ám ez egyúttal a lista hátránya is, hiszen ha a lista valamelyik mutatója sérül, elveszik a szekvenciális visszakereshetőség.
 

Fajtái

• gyűrűs lista (cirkuláris, zárt) - ha az utolsó elem (mutató) a kezdőpontra mutat,

• nyíltvégű lista - első és utolsó eleme végjel,

• kétirányú lista (szimmetrikus) - ha visszafelé is léphetünk benne, mert a mutatók visszafelé is mutatnak,

• rendezett lista - az elemek valamilyen logikai szempont szerint rendezettek,

• fejelt lista - előre "félig elkészített" lista, mert van 1 fejrésze, amely az első és utolsó elem mutatóját tartalmazza, az adatrész azonban még üres,

• többszörös (multi)lista - a listaelemek további listák kiindulópontjai.