Lista

A HupWiki-ből...

A lista homogén, szekvenciális (lineáris), dinamikus adatszerkezet. A homogén azt jelenti, hogy csak egyfajta elemet tud tárolni, a szekvenciális azt jelenti, hogy egymás után vannak az elemek befűzve. A következő fajtái vannak: láncolt lista, gyűrű, kétirányú lista, összetett lista.

• Láncolt lista

Minden eleme pontosan egy mutatót tartalmaz, egy másik ugyanolyan típusú elemre, illetve egy adott típusú adatot. A lánc első elemének a címét a lista feje tartalmazza. A listafej nem tartalmaz információs részt. A lánc utolsó elemének mutatója NULL-t tartalmaz.

    class Elem {
        Típus Adat;
        Elem *Következő;
    }
    class Lista {
        Elem *Fej;
    }

Valahogy így lehet ábrázolni:

|Fej|-->|1.elem|-->|2.elem|-->...-->|n.elem|-->NULL

• Gyűrűk

A gyűrűnek az a lényege, hogy az utolsó elem nem a NULL-ra fog mutatni, hanem az első elemre, így kört hozva létre. Ennek az az előnye, hogy bármelyik elemből bármelyik elemet el lehet érni. A gyűrű bejárásánál azonban nagyon figyelnünk kell, ugyanis a lista végét már nem jelzi NULL pointer.

• Kétirányú láncolt listák

Ha mindegyik elemből nem csak a következő elemet lehet elérni, hanem az előzőt is, tehát egy előzőre mutató pointere is van az elemnek, akkor kétirányú listáról beszélünk.

• Összetett listák

Az összetett lista elemei lehetnek adatelemek és újabb listák is.