Hoe kies je de juiste gegevensstructuur voor een probleem?

Question

Accepted Answer

Kies de structuur waarvan de **meest voorkomende bewerkingen het goedkoopst** zijn voor uw toegangspatroon. Begin met het opsommen van de bewerkingen die u gaat uitvoeren, schat hun frequentie, en match ze vervolgens met de sterktes van een structuur.

## Waarom het belangrijk is

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

## Bewerkingen aan complexiteit koppelen

| Behoefte | Beste structuur | Sleutelkostenoperatie |
|---|---|---|
| Willekeurige toegang per index | dynamic array | O(1) |
| Lookup op sleutel | hash map | O(1) avg |
| Gesorteerd + bereikquery's | balanced BST | O(log n) |
| Min/max herhaaldelijk | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Prefix-zoeken | trie | O(L) |

## Voorbeeldredenering

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

## Waarom het belangrijk is

Goed kiezen is vaak het verschil tussen een O(n) en een O(n²) oplossing — de grootste hefboom op prestaties.

Interviewers testen precies deze redenering: ze willen zien dat u vereisten aan bewerkingskosten koppelt, niet dat u structuren uit het hoofd leert.

Behoefte	Beste structuur	Sleutelkostenoperatie
Willekeurige toegang per index	dynamic array	O(1)
Lookup op sleutel	hash map	O(1) avg
Gesorteerd + bereikquery's	balanced BST	O(log n)
Min/max herhaaldelijk	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Prefix-zoeken	trie	O(L)