Ugrás a tartalomhoz

collection data type

A Wikiszótárból, a nyitott szótárból
(collection (abstract data type) szócikkből átirányítva)


Főnév

collection data type (tsz. collection data types)

  1. (informatika) A kollekció (collection) absztrakt adatszerkezet (ADT) egy olyan általános „doboz”, amiben egy vagy több azonos típusú elemet tárolunk, és amely fölött meghatározott műveletek (insert, delete, search, iterate stb.) értelmezettek. A kollekció‐ADT olyan általános osztály, amely különféle konkrét adatszerkezeteket foglal magában (lista, halmaz, térkép, priorizált sor stb.), közös jellemzőjük, hogy az elemek rendezve vagy rendezetlenül, de csoportosan tárolódnak.


1. A kollekció‐ADT típusai

ADT típusa Leírás
Lista (Sequence) Elemek sorrendje fontos; megőrizzük a beszúrási sorrendet, vagy konkrét indexen tudunk műveletet végezni.
Verem (Stack) LIFO viselkedés (utolsóként be, elsőként ki); specializált lista, ahol csak a „végén” engedünk beszúrást/kivételt.
Sor (Queue) FIFO viselkedés (elsőként be, elsőként ki); specializált lista, ahol csak fej/vég műveletek értelmezettek.
Halmaz (Set) Ismétlődésmentes elemek gyűjteménye, nem fontos a beszúrási sorrend.
Többszörös halmaz (Multiset/Bag) Engedélyezi az ismétlődő elemeket, de nem tartja meg a sorrendet.
Térkép (Map/Dictionary) Kulcs–érték párokat tárolunk; minden kulcshoz egy érték tartozik, a kulcsok egyediek (mint egy halmaz).
Prioritási sor (Priority Queue) Minden elemhez prioritást rendelünk; a „legmagasabb prioritású” elem kerül először ki.


2. Műveletek és szpecifikáció

2.1. Közös műveletek minden kollekciónál

  • Create(): új, üres kollekció létrehozása.
  • isEmpty() → bool: igaz, ha nincs benne elem.
  • size() → int: elemek száma.
  • clear(): minden elem törlése, üres kollekció.

2.2. Beszúrás és törlés

  • add(x) vagy insert(x): x beszúrása a kollekcióba.
  • remove(x): x törlése (set): ha létezik, eltávolítjuk.
  • deleteAt(i) (sequence): adott indexű elem eltávolítása.
  • push(x)/pop() (stack), enqueue(x)/dequeue() (queue), offer(x)/poll() (priority queue).

2.3. Lekérdezés és keresés

  • contains(x): igaz, ha x eleme a kollekciónak.
  • get(i) (sequence): i‐edik elem visszaadása.
  • peek() (stack/queue): a következő eltávolítandó elem megtekintése anélkül, hogy kiven­nénk.
  • find(key) (map): adott kulcshoz tartozó érték lekérése.

2.4. Iterálás

  • iterator() vagy forEach(f): sorban végigjárja az összes elemet.
  • keys(), values(), entries() (map): kulcsok, értékek, kulcs–érték párok elkérése.


3. Implementációk és komplexitások

ADT Gyakori implementációk Enqueue/insert Dequeue/remove Search/lookup
Sequence tömb (array-list), láncolt lista O(1) amort. / O(n) O(n) / O(1) head O(1) / O(n)
Stack tömb, láncolt lista O(1) O(1) O(n)
Queue körkörös tömb, kettős láncolt lista O(1) O(1) O(n)
Set hash‐tábla, kiegyensúlyozott fa (tree) O(1) / O(log n) O(1) / O(log n) O(1) / O(log n)
Multiset hash‐tábla + számlálók, fában többszörösítés O(1) / O(log n) O(1) / O(log n) O(1) / O(log n)
Map hash‐tábla (unordered_map), fa (map) O(1) / O(log n) O(1) / O(log n) O(1) / O(log n)
PrioQueue bináris kupac, fibonacci kupac O(log n) O(log n) O(n) vagy O(log n)
  • Tömb alapú sequence: std::vector (C++), ArrayList (Java), dinamikusan reallokálódik; gyors véletlen elérés O(1).
  • Láncolt lista: std::list (C++), LinkedList (Java); gyors beszúrás/kivétel ismerős pozíción O(1), de drága véletlen elérés O(n).
  • Halmaz:
    • HashSet: std::unordered_set (C++), HashSet (Java); várható O(1) beszúrás/kivétel, de rossz hash esetén O(n).
    • TreeSet: std::set (C++), TreeSet (Java); garantált O(log n) műveletek, rendezett kulcsok.
  • Térkép:
    • HashMap: std::unordered_map, HashMap; key → value, O(1) átlagosan.
    • TreeMap: std::map, TreeMap; rendezett kulcs, O(log n).
  • Prioritási sor:
    • binary_heap (std::priority_queue C++); push/pop O(log n).
    • pairing/fibonacci heap: amortizált O(1) beillesztés, O(log n) kivétel.


4. Mikor melyik kollekciót válasszuk?

  1. Sorrend‐megőrzés kell → Sequence (vector vagy linked list)
  2. Stack vagy Queue sémát követünk → Stack / Queue
  3. Gyors ellenőrzés, hogy szerepel-e egy elem → Set
  4. Kulcs–érték párokban tárolunk → Map
  5. Legmagasabb prioritású kell először → PriorityQueue
  6. Duplikátumok engedélyezettek, de sorrend nem fontos → Multiset/Bag


5. Nyelvi támogatás és könyvtárak

  • C++ STL:
    • std::vector<T>, std::list<T>, std::forward_list<T>
    • std::deque<T> (double‐ended queue)
    • std::set<T>, std::multiset<T>, std::unordered_set<T>
    • std::map<K,V>, std::multimap<K,V>, std::unordered_map<K,V>
    • std::priority_queue<T>
  • Java Collections:
    • ArrayList, LinkedList, Vector, Stack, Deque
    • HashSet, TreeSet, LinkedHashSet
    • HashMap, TreeMap, LinkedHashMap, Hashtable
    • PriorityQueue
  • Python:
    • list, collections.deque
    • set, frozenset, collections.Counter (multiset)
    • dict
    • heapq (min‐heap)


6. Iterátorok és funkcionális műveletek

Modern kollekció‐API‐k iterátorokon vagy streameken keresztül is biztosítanak:

  • forEach, map, filter, reduce: pl. Java Streams, C++ ranges, Python list comprehensions.
  • Iterator interfész: egységes mód végigjárni bármely kollekciót anélkül, hogy a belső szerkezetre hagyatkozunk.


7. Összefoglalás

A kollekció ADT az algoritmusok és szoftvertervezés egyik legfontosabb építőköve. Azáltal, hogy absztrakt módon definiálunk műveleteket (insert, delete, search, iterate stb.), függetleníteni tudjuk az algoritmuslogikát a konkrét belső reprezentációtól. A gyakorlatban:

  • Megfelelő kollekció‐ADT kiválasztása kritikus a teljesítmény és erőforrás‐felhasználás optimalizálásához.
  • A könyvtári implementációk (STL, Java Collections, Python built‐ins) használata erősen javasolt a saját, hibalehetőségektől mentes fejlesztéshez.
  • A funkcionális és iterátor‐alapú megközelítések lehetővé teszik a kód deklaratív, tömör és biztonságos felépítését.

A kollekciók ismerete és helyes alkalmazása minden komolyabb szoftverprojekt alapja: adatgyűjtés, feldolgozás, kommunikáció, párhuzamos végrehajtás és felhasználói interakciók során is szükség van a megfelelő ADT‐k használatára.


A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=collection_data_type&oldid=3500275”