list data type

Angol

Főnév

list data type (tsz. list data types)

1. (informatika) A lista (List) absztrakt adatszerkezet (ADT, Abstract Data Type) egy olyan sorozat, amelyben az elemek egy meghatározott sorrendben vannak tárolva, és amely fölött a következő alapműveletek értelmezettek:

1. Létrehozás (Create) Egy új, üres listát hozunk létre.
2. Üresség ellenőrzése (isEmpty) Visszaadja, hogy a lista jelenleg üres-e.
3. Méret lekérdezése (Size) Visszaadja az elemek számát a listában.
4. Beszúrás (Insert vagy Add)
   • position-tól függően: adott indexnél vagy csomópont előtt/három
   • végére (append)
   • elejére (prepend) Bemásolunk vagy mutatót átállítunk, hogy új elemet illesszünk be.
5. Eltávolítás (Remove vagy Delete)
   • Adott indexű elem törlése
   • Érték alapján törlés
   • Első, utolsó eltávolítása
6. Lekérdezés (Get vagy At)
   • Az adott indexű elem tartalmának olvasása
   • Adott érték keresése (Find)
7. Módosítás (Set vagy Update)
   • Adott indexű elem értékének beállítása
8. Iterálás (Iterator vagy Traversal) – Végigjárhatjuk a lista elemeit lineárisan.
9. Törlés (Clear vagy DeleteAll) – A lista összes elemét felszabadítjuk, és üres listává alakítjuk.

---

Miért hasznos a lista ADT?

• Dinamikus méret: tetszőleges számú elem tárolható, és beszúráskor/törléskor a lista rugalmasan nő vagy csökken.
• Sorrend megőrzése: a beszúrás sorrendjét megtartva bármely pozícióban lehet operálni.
• Különböző műveleti komplexitás: implementációtól függően optimális lehet a végi beszúrás, közepes beszúrás, végi eltávolítás vagy véletlen elérés.

---

Implementációs lehetőségek

1. Egyszeres láncolt lista (Singly Linked List)

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.

2. Kétszeres láncolt lista (Doubly Linked List)

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.

3. Statikus tömb alapú lista

Felépítés:

• Egy statikus tömb az elemeknek.
• size a tömb hossza, length a tényleges lista-méret.
• head index (az első használatban lévő elem pozíciója).
• Egy “free list” kezelheti az üres indexeket.
• Minden tételhez tartozik egy „nextIndex” mező, ami a tömbön belüli következő elem indexét tárolja (-1 végpont).

Műveletek:

• append: nextIndex[tail] = newIdx; tail = newIdx;
• removeFirst: head = nextIndex[head];
• 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.

4. Dinamikus tömb (array-list vagy vector)

Felépítés:

• Egy nyers tömb data[], capacity és length változó.
• Teljes tömb reallokálással nő (pl. kétszeresére), ha betelik.

Műveletek:

• append: ha length < capacity, data[length++] = x; különben resize() → új tömb, másolás, majd beszúrás.
• insertAt(i): memmove/másolás jobbra a data[i..length) → data[i] = 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[i] 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.

---

Műveleti bonyolultság összefoglalva

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).

---

Válogatás a gyakorlatban

• Java:
  • ArrayList<E> (dinamikus tömb)
  • LinkedList<E> (kétszeres láncolt lista + kettős végi mutatók)
• C++ STL:
  • std::vector<T> (dinamikus tömb)
  • std::list<T> (kétszeres láncolt lista)
• Python:
  • list (dinamikus tömb)
  • collections.deque (kétirányú körkörös puffer)

---

Mikor melyiket válasszuk?

• Gyakori véletlen olvasás/írás: dinamikus tömb (vector, ArrayList).
• Nagyon sok közepes pozíciós beszúrás/törlés: láncolt lista (std::list, bekötéses puffer).
• Fix maximális elemszám, egyszerű láncolt kapcsolat: statikus tömb + indexes lista.
• FIFO vagy LIFO speciális változatai: sor (queue) ↔ FIFO lista, verem (stack) ↔ LIFO lista.

---

Összefoglalás

A lista ADT a programozás alapvető eszköze, amely:

• Rugalmas méretet és sorrendiség‐megőrzést ad,
• Egyszerű absztrakt műveletek mentén definiálható (insert, remove, get, set, iterate),
• Többféle implementáció kínál különböző teljesítmény‐ és memória‐jellemzőkkel,
• Széles körű alkalmazás: adatok sorba rendezése, memóriakezelés, komplexabb adatszerkezetek (stack, queue, hash bucket, stb.) építőeleme.

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.

További információk

• list data type - Szótár.net (en-hu)
• list data type - Sztaki (en-hu)
• list data type - Merriam–Webster
• list data type - Cambridge
• list data type - WordNet
• list data type - Яндекс (en-ru)
• list data type - Google (en-hu)
• list data type - Wikidata
• list data type - Wikipédia (angol)