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.