Hvordan velger du den riktige datastrukturen for et problem?

Question

Accepted Answer

Velg strukturen der **de hyppigst brukte operasjonene er billigst** for ditt tilgangsmønster. Start med å liste opp operasjonene du vil utføre, estimer hyppigheten deres, og matcher dem deretter til strukturens styrker.

## Beslutningssjekkliste

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

## Matcher operasjoner til kompleksitet

| Behov | Beste struktur | Nøkkeloperasjonskostnad |
|---|---|---|
| Tilfeldig tilgang etter indeks | dynamic array | O(1) |
| Oppslag etter nøkkel | hash map | O(1) avg |
| Sortert + områdespørringer | balanced BST | O(log n) |
| Min/maks gjentatt | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Prefikssøk | trie | O(L) |

## Eksempelresonnement

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

## Hvorfor det er viktig

Å velge riktig er ofte forskjellen mellom en O(n) og en O(n²) løsning — den største enkelteffekten på ytelse.

Intervjuere tester nøyaktig denne resonneringen: de vil se at du mapper krav til operasjonskostnader, ikke at du memorerer strukturer.

Behov	Beste struktur	Nøkkeloperasjonskostnad
Tilfeldig tilgang etter indeks	dynamic array	O(1)
Oppslag etter nøkkel	hash map	O(1) avg
Sortert + områdespørringer	balanced BST	O(log n)
Min/maks gjentatt	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Prefikssøk	trie	O(L)