Kako izbereš pravo podatkovno strukturo za nalogo?

Question

Accepted Answer

Izberi strukturo, katere **najpogostejše operacije so najcenejše** za tvoj vzorec dostopa. Začni s seznamom operacij, ki jih boš izvajal, oceni njihovo pogostost, nato pa jih uskladi s prednostmi strukture.

## Kontrolni seznam odločitve

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Uskladi operacije s kompleksnostjo

| Potreba | Najboljša struktura | Stroški ključne operacije |
|---|---|---|
| Naključni dostop po indeksu | dynamic array | O(1) |
| Iskanje po ključu | hash map | O(1) povprečno |
| Sortirano + poizvedbe obsega | balanced BST | O(log n) |
| Min/max večkrat | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Iskanje s predpono | trie | O(L) |

## Primer sklepanja

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Zakaj je to važno

Pravilna izbira je pogosto razlika med O(n) in O(n²) rešitvijo — najpomembnejši faktor za zmogljivost.

Interviuji testirajo natanko to sklepanje: želijo videti, da operacije mapiraš na stroške, ne da si strukturo samo zapomnil.

Potreba	Najboljša struktura	Stroški ključne operacije
Naključni dostop po indeksu	dynamic array	O(1)
Iskanje po ključu	hash map	O(1) povprečno
Sortirano + poizvedbe obsega	balanced BST	O(log n)
Min/max večkrat	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Iskanje s predpono	trie	O(L)