ADT Referencia Útmutató

Tartalomjegyzék

1. List (Lista)
2. Stack (Verem)
3. Queue (Sor)
4. Set (Halmaz)
5. Dictionary/Map (Szótár)
6. Hash Table (Hash Tábla)

---

List (Lista)

Mi ez?

Rendezett elemek sorozata, ahol minden elemnek van egy indexe (pozíciója).

Mire használható?

• Adatok sorrendben tárolása
• Indexszel való gyors hozzáférés
• Dinamikus méretű tömbök helyett
• Amikor fontos a sorrend

Példa működésre

Lista: [10, 20, 30, 40]
insertBack(50)  → [10, 20, 30, 40, 50]
get(2)          → 30
remove(1)       → [10, 30, 40, 50]

Műveletek komplexitása

Array List (Dinamikus tömb)

Művelet	Komplexitás	Magyarázat
get(index)	O(1)	Direkt memória hozzáférés
set(index, value)	O(1)	Direkt memória írás
insertBack(value)	O(1) amortized	Átlagosan konstans, néha resize O(n)
insertFront(value)	O(n)	Minden elemet el kell tolni
insert(index, value)	O(n)	Index utáni elemeket tolni kell
removeBack()	O(1)	Egyszerű size csökkentés
removeFront()	O(n)	Minden elemet előre kell tolni
remove(index)	O(n)	Elemek tömörítése szükséges
size()	O(1)	Tárolt változó

Linked List (Láncolt lista)

Művelet	Komplexitás	Magyarázat
get(index)	O(n)	Végig kell menni a láncon
set(index, value)	O(n)	Előbb meg kell találni az elemet
insertBack(value)	O(1)*	Ha van tail pointer
insertFront(value)	O(1)	Új head beállítása
insert(index, value)	O(n)	Index-ig navigálás + beszúrás
removeBack()	O(n)	Utolsó előtti elem megtalálása kell
removeFront()	O(1)	Head átállítása
remove(index)	O(n)	Navigálás + pointer átállítás
size()	O(1) vagy O(n)	Attól függ, tároljuk-e

---

Stack (Verem)

Mi ez?

LIFO (Last In, First Out) adatszerkezet - az utoljára betett elem jön ki először.

Mire használható?

• Függvényhívások kezelése (call stack)
• Visszalépés (undo) implementálása
• Zárójelek ellenőrzése
• Depth-First Search (DFS)
• Kifejezések kiértékelése (postfix, prefix)

Példa működésre

Stack: []
push(10)    → [10]
push(20)    → [10, 20]
push(30)    → [10, 20, 30]
pop()       → 30, Stack: [10, 20]
peek()      → 20
pop()       → 20, Stack: [10]

Műveletek komplexitása

Művelet	Komplexitás	Magyarázat
push(value)	O(1)	Tetejére helyezés
pop()	O(1)	Tetejéről levétel
peek()	O(1)	Tetejét megnézés levétel nélkül
isEmpty()	O(1)	Size check
size()	O(1)	Tárolt változó

Implementáció: Általában Array List vagy Linked List használatával.

---

Queue (Sor)

Mi ez?

FIFO (First In, First Out) adatszerkezet - az először betett elem jön ki először.

Mire használható?

• Feladatok sorbaállítása (task scheduling)
• Breadth-First Search (BFS)
• Printer queue (nyomtatási sor)
• Message queues (üzenet sorok)
• Level-order traversal (fa bejárás)

Példa működésre

Queue: []
enqueue(10)    → [10]
enqueue(20)    → [10, 20]
enqueue(30)    → [10, 20, 30]
dequeue()      → 10, Queue: [20, 30]
peek()         → 20
dequeue()      → 20, Queue: [30]

Műveletek komplexitása

Array-based (Circular Buffer)

Művelet	Komplexitás	Magyarázat
enqueue(value)	O(1) amortized	Végére hozzáadás
dequeue()	O(1)	Elejéről elvétel
peek()	O(1)	Elején lévő elem
isEmpty()	O(1)	Size check
size()	O(1)	Tárolt változó

Linked List-based

Művelet	Komplexitás	Magyarázat
enqueue(value)	O(1)	Tail-nél beszúrás
dequeue()	O(1)	Head-nél törlés
peek()	O(1)	Head elem
isEmpty()	O(1)	Head == null check
size()	O(1)	Tárolt változó

---

Set (Halmaz)

Mi ez?

Egyedi elemek rendezetlen gyűjteménye - nincs duplikátum, nincs sorrend.

Mire használható?

• Duplikátumok eltávolítása
• Tagsági teszt (benne van-e egy elem?)
• Halmazműveletek (unió, metszet, különbség)
• Egyedi értékek gyűjtése

Példa működésre

Set: {}
add(10)        → {10}
add(20)        → {10, 20}
add(10)        → {10, 20}  (már benne van)
contains(20)   → true
remove(10)     → {20}

Műveletek komplexitása

Hash Set

Művelet	Komplexitás	Magyarázat
add(value)	O(1) average	Hash táblával
remove(value)	O(1) average	Hash keresés
contains(value)	O(1) average	Hash lookup
size()	O(1)	Tárolt változó

Tree Set (BST-based)

Művelet	Komplexitás	Magyarázat
add(value)	O(log n)	Fa beszúrás
remove(value)	O(log n)	Fa törlés
contains(value)	O(log n)	Fa keresés
size()	O(1)	Tárolt változó

---

Dictionary/Map (Szótár)

Mi ez?

Kulcs-érték párok gyűjteménye. Minden kulcs egyedi, és egy értékhez kapcsolódik.

Mire használható?

• Gyors keresés kulcs alapján
• Konfigurációs beállítások tárolása
• Cachelés
• Szavak számlálása (word frequency)
• Objektumok azonosítókkal való tárolása

Példa működésre

Dictionary: {}
put("név", "Anna")      → {"név": "Anna"}
put("kor", "25")        → {"név": "Anna", "kor": "25"}
get("név")              → "Anna"
put("név", "Béla")      → {"név": "Béla", "kor": "25"}  (felülírás)
remove("kor")           → {"név": "Béla"}

Műveletek komplexitása

Hash Map (Hash Tábla)

Művelet	Komplexitás	Magyarázat
put(key, value)	O(1) average	Hash beszúrás
get(key)	O(1) average	Hash keresés
remove(key)	O(1) average	Hash törlés
containsKey(key)	O(1) average	Hash lookup
size()	O(1)	Tárolt változó

Tree Map (BST-based)

Művelet	Komplexitás	Magyarázat
put(key, value)	O(log n)	Fa beszúrás
get(key)	O(log n)	Fa keresés
remove(key)	O(log n)	Fa törlés
containsKey(key)	O(log n)	Fa keresés
size()	O(1)	Tárolt változó

---

Hash Table (Hash Tábla)

Mi ez?

Implementációs technika Dictionary/Map és Set megvalósításához, hash függvény használatával.

Mire használható?

• Gyors keresés, beszúrás, törlés O(1) időben
• HashMap és HashSet implementálása
• Gyorsítótárazás
• Egyediség ellenőrzés

Hogyan működik?

1. Hash függvény: h(key) → index - a kulcsból index-et generál
2. Bucket array: tömb, ahol az elemek tárolódnak
3. Collision resolution: ütközések kezelése (chaining vagy open addressing)

Példa működésre

Hash Table (size=8, h(x) = x*5 mod 8):

put(1, "A"):  h(1) = 5 → tömb[5] = (1, "A")
put(2, "B"):  h(2) = 2 → tömb[2] = (2, "B")
put(9, "C"):  h(9) = 5 → ütközés! Chaining: tömb[5] → [(1,"A"), (9,"C")]
get(9):       h(9) = 5 → keresés a tömb[5] láncban → "C"

Hash Függvények

Standard integer hash: h(x) = x * a mod N

• ahol a és N relatively prime (nincs közös osztó)
• Példa: h(x) = x * 5 mod 8

Miért kell relatively prime?

Ha a = 4, N = 8:
h(0) = 0
h(1) = 4
h(2) = 0  ← Ütközés!
h(3) = 4  ← Ütközés!
Csak 0 és 4 indexeket használja → rossz eloszlás

Collision Resolution (Ütközéskezelés)

1. Chaining (Láncolás)

Minden bucket egy linked list.

Index 0: → null
Index 1: → null
Index 2: → (key=2, val="B") → (key=10, val="D") → null
Index 3: → null

Műveletek:

Művelet	Average Case	Worst Case
put(key, value)	O(1)	O(n)
get(key)	O(1)	O(n)
remove(key)	O(1)	O(n)

Pszeudokód - Chaining:

put(key, value):
    index = h(key)
    for each (k, v) in buckets[index]:
        if k == key:
            v = value  // felülírás
            return
    buckets[index].addFront(key, value)  // új elem
    size++
    if size > N * loadFactor:
        resize()

get(key):
    index = h(key)
    for each (k, v) in buckets[index]:
        if k == key:
            return v
    return null

remove(key):
    index = h(key)
    for each (k, v) in buckets[index]:
        if k == key:
            buckets[index].remove((k, v))
            size--
            return

2. Linear Probing (Nyílt címzés)

Ha ütközés van, a következő szabad helyre tesszük.

Beszúrás x=2 (h(2)=5):
Index:  0  1  2  3  4  5  6  7
Value: [ ][ ][ ][ ][ ][X][ ][ ]

Beszúrás x=10 (h(10)=5, de foglalt):
Index:  0  1  2  3  4  5  6  7
Value: [ ][ ][ ][ ][ ][X][Y][ ]  ← Y ide került

Műveletek:

Művelet	Average Case	Worst Case
put(key, value)	O(1)	O(n)
get(key)	O(1)	O(n)
remove(key)	O(1)	O(n)

Pszeudokód - Linear Probing:

put(key, value):
    index = h(key)
    while buckets[index] != null and buckets[index].key != key:
        index = (index + 1) mod N  // következő hely
    if buckets[index] == null:
        size++
    buckets[index] = (key, value)
    if size > N * loadFactor:
        resize()

get(key):
    index = h(key)
    while buckets[index] != null:
        if buckets[index].key == key:
            return buckets[index].value
        index = (index + 1) mod N
    return null

remove(key):
    index = h(key)
    while buckets[index] != null:
        if buckets[index].key == key:
            buckets[index] = DELETED_MARKER  // speciális jelölés
            size--
            return
        index = (index + 1) mod N

Load Factor és Resizing

Load Factor: α = n / N (elemek száma / bucket-ek száma)

• Ha α > 0.75 (chaining) vagy α > 0.5 (linear probing) → resize
• Resize: Új, nagyobb tömb (pl. 2N), minden elem újra-hash-elése

resize():
    oldBuckets = buckets
    N = N * 2
    buckets = new Array[N]
    size = 0
    for each bucket in oldBuckets:
        for each (key, value) in bucket:
            put(key, value)  // újra hash-elés

---

Gyors Összehasonlítás

ADT	Fő műveletek	Average Complexity	Mikor használd
List	get, set, insert	O(1) / O(n)	Indexelt hozzáférés, sorrend fontos
Stack	push, pop	O(1)	LIFO, visszalépés, DFS
Queue	enqueue, dequeue	O(1)	FIFO, feladat sorba állítás, BFS
Set	add, contains	O(1) hash, O(log n) tree	Egyediség, tagsági teszt
Dictionary	put, get	O(1) hash, O(log n) tree	Kulcs-érték párok, gyors keresés
Hash Table	put, get, remove	O(1) average	Háttérben Map/Set implementáláshoz

---

Gyakorlati Tippek

Mikor melyiket válasszuk?

1. Kell index-elt hozzáférés? → List (ArrayList)
2. Csak az elején/végén műveletek? → LinkedList vagy Stack/Queue
3. LIFO (utolsó be, első ki)? → Stack
4. FIFO (első be, első ki)? → Queue
5. Egyedi elemek, sorrend nem számít? → Set (HashSet gyors, TreeSet rendezett)
6. Kulcs-érték párok? → Map (HashMap gyors, TreeMap rendezett)
7. Gyors keresés/beszúrás/törlés kell? → HashMap/HashSet

Implementációs választások

Követelmény	Válassz
Gyors random access	ArrayList
Gyakori beszúrás/törlés az elején	LinkedList
O(1) keresés	HashMap / HashSet
Rendezett elemek	TreeMap / TreeSet
Fix méretű gyűjtemény	Array
LIFO műveletek	Stack
FIFO műveletek	Queue

---

Példa: Adatszerkezet Választás Gyakorlati Feladatokhoz

1. Bag of Words (Szavak számlálása)

Feladat: Számold meg, hányszor fordul elő minden szó egy szövegben.
Megoldás: HashMap<String, Integer>

Miért? 
- Szó (kulcs) → Gyakoriság (érték) párok
- O(1) hozzáférés/frissítés
- n szó esetén O(n) komplexitás

2. Sliding Window (Csúszó ablak)

Feladat: Tartsd nyilván az utolsó k elemet, add vissza összegüket O(1)-ben.
Megoldás: Queue + változó az összeghez

Miért?
- FIFO: régi elemek kiesnek, újak bejönnek
- Összeg: sum += új_elem - régi_elem

3. Undo/Redo

Feladat: Implementálj visszavonás/újra funkciót.
Megoldás: 2 Stack (undo stack, redo stack)

Miért?
- LIFO: utolsó művelet visszavonása
- Undo: pop from undo_stack, push to redo_stack
- Redo: pop from redo_stack, push to undo_stack

4. LRU Cache (Least Recently Used)

Feladat: Cache fix mérettel, ritkán használt elemek kiesnek.
Megoldás: HashMap + DoublyLinkedList

Miért?
- HashMap: O(1) keresés
- DoublyLinkedList: O(1) mozgatás elején/végén
- Használatkor: mozgatás a lista elejére

---

Készítette: Baki Botond(A formázást a Claude AI készítette)

The material is not originally of the author's.
     no rights can be derived from material(as it is considered general knowledge in the context of the profession)

Verzió: 1.0
Utolsó frissítés: 2025 02 13