Hvordan vælger du den rigtige datastruktur til et problem?

Question

Accepted Answer

Vælg den struktur, hvis **hyppigste operationer er billigst** for dit adgangsmønster. Start med at liste de operationer, du vil udføre, estimér deres frekvens, og match dem derefter til strukturens styrker.

## Tjekliste til beslutningstagning

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

## Match operationer med kompleksitet

| Behov | Bedste struktur | Vigtigste ops pris |
|---|---|---|
| Tilfældig adgang efter indeks | dynamic array | O(1) |
| Opslag efter nøgle | hash map | O(1) avg |
| Sorteret + områdeforespørgsler | balanced BST | O(log n) |
| Min/max gentagne gange | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Præfiksøgning | trie | O(L) |

## Eksempel på ræsonnement

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

At vælge rigtigt er ofte forskellen mellem en O(n) og en O(n²) løsning — det største pres på ydeevne.

Interviewere tester netop denne ræsonnering: de vil se dig mappe krav til operationsomkostninger, ikke bare memorere strukturer.

Behov	Bedste struktur	Vigtigste ops pris
Tilfældig adgang efter indeks	dynamic array	O(1)
Opslag efter nøgle	hash map	O(1) avg
Sorteret + områdeforespørgsler	balanced BST	O(log n)
Min/max gentagne gange	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Præfiksøgning	trie	O(L)