list data type (tsz. list data types)
Felépítés: minden csomópont tartalmaz egy „érték” és egy next mutatót a következő csomópontra; a lista fejét (head) és opcionálisan a végét (tail) tároljuk. Műveletek:
prepend: új csomópont a fej elé (O(1)).append: ha van tail, akkor ott kötjük be (O(1)); ha nincs, végig kell menni O(n)).insertAt(index): addig követjük a next-et, amíg az index-1-hez nem érünk (O(k)); ott illesztünk be.removeAt(index): ugyanígy O(k) a pozíció megtalálása és a következő átállítása.getAt(index): pozícióig bejárás O(k).Előnyök: dinamikus, minden beszúrás/eltávolítás pozíción kívüli pointermódosítás, nincs tömb-reallokáció. Hátrányok: véletlen elérés lassú (O(n)), memóriában minden elem külön allokáció, pointer-overhead.
Felépítés: minden elemnek prev és next mutatója van. Tároljuk a head és tail mutatókat. Műveletek:
remove(node): a node->prev->next = node->next, node->next->prev = node->prev egyszerű O(1) művelet.insertBefore(node, newNode) vagy insertAfter(node, newNode) szintén O(1).Előnyök: két irányba bejárható, közvetlen eltávolítás adott mutatóból O(1). Hátrányok: dupla pointer-overhead, nagyobb memória-igény.
Felépítés:
size a tömb hossza, length a tényleges lista-méret.head index (az első használatban lévő elem pozíciója).-1 végpont).Műveletek:
append: nextIndex = newIdx; tail = newIdx;removeFirst: head = nextIndex;insertAt/removeAt: indexmutatók láncolása.Előnyök: nem kell dinamikus allokáció minden elemhez, memóriacímek tömbben vannak, viszonylag jó cache‐locality. Hátrányok: fix kapacitás (vagy bonyolult reallokáció), a „next” mező memóriát fogyaszt.
Felépítés:
data, capacity és length változó.Műveletek:
append: ha length < capacity, data = x; különben resize() → új tömb, másolás, majd beszúrás.insertAt(i): memmove/másolás jobbra a data = x, length++ (O(n−i) másolás).removeAt(i): memmove(data+i, data+i+1, (length−i−1)*sizeof) → length--.getAt(i): közvetlen data O(1).Előnyök: konstans idejű véletlen elérés, jól skálázódik (amortizált O(1) az append esetén). Hátrányok: közepes beszúrás/törlés O(n), reallokáció overhead.
| ADT | beszúrás elejére | beszúrás végére | beszúrás közepére | törlés közepéről | véletlen elérés | iterálás |
|---|---|---|---|---|---|---|
| Singly LL | O(1) | O(n) vagy O(1)¹ | O(n) | O(n) | O(n) | O(n) |
| Doubly LL | O(1) | O(1) | O(n) | O(1) | O(n) | O(n) |
| Array-list | O(n) | amort. O(1) | O(n) | O(n) | O(1) | O(n) |
| Static array | O(n) | O(1) | O(n) | O(n) | O(1) | O(n) |
¹ – ha tároljuk a tail mutatót, akkor a végi beszúrás O(1).
ArrayList<E> (dinamikus tömb)LinkedList<E> (kétszeres láncolt lista + kettős végi mutatók)std::vector<T> (dinamikus tömb)std::list<T> (kétszeres láncolt lista)list (dinamikus tömb)collections.deque (kétirányú körkörös puffer)
vector, ArrayList).std::list, bekötéses puffer).queue) ↔ FIFO lista, verem (stack) ↔ LIFO lista.
A lista ADT a programozás alapvető eszköze, amely:
A gyakorlott fejlesztő tudja:
a lista ADT‐t mindig az adott probléma műveleti profilja alapján választjuk ki (gyakori véletlen elérés vs. gyakori beszúrás/törlés), valamint a rendelkezésre álló memóriamanagement-módszerek, cache-közelség és egyszerűség mentén.
Ezzel a tudással hatékonyan tervezhetünk és valósíthatunk meg dinamikus, sorrendi adatszerkezeteket bármely programnyelven vagy környezetben.