Kako odabirate pravu strukturu podataka za problem?

Question

Accepted Answer

Odaberite strukturu čije su **najčešće operacije najjeftinije** za vašu vrstu pristupa. Počnite nabrajanjem operacija koje ćete izvoditi, procijenite njihovu učestalost, a zatim ih usporedite sa snagama strukture.

## Popis za provjeru odluke

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

## Usporedite operacije sa složenošću

| Potreba | Najbolja struktura | Ključni trošak operacije |
|---|---|---|
| Slučajan pristup po indeksu | dynamic array | O(1) |
| Pretraživanje po ključu | hash map | O(1) avg |
| Sortirano + upiti raspona | balanced BST | O(log n) |
| Min/max ponavljano | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Pretraživanje prefiksa | trie | O(L) |

## Primjer zaključivanja

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

## Zašto je važno

Ispravan odabir često je razlika između O(n) i O(n²) rješenja — najveća poluga na performanse.

Interviueri testiraju upravo ovo zaključivanje: žele vidjeti kako mapiramo zahtjeve na troškove operacija, ne da memorizirate strukture.

Potreba	Najbolja struktura	Ključni trošak operacije
Slučajan pristup po indeksu	dynamic array	O(1)
Pretraživanje po ključu	hash map	O(1) avg
Sortirano + upiti raspona	balanced BST	O(log n)
Min/max ponavljano	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Pretraživanje prefiksa	trie	O(L)