Hur väljer du rätt datastruktur för ett problem?

Question

Accepted Answer

Välj strukturen vars **mest frekventa operationer är billigast** för ditt åtkomstmönster. Börja med att lista de operationer du kommer att utföra, uppskatta deras frekvens, och matcha dem sedan till strukturens styrkor.

## En checklistor för beslut

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

## Matcha operationer till komplexitet

| Behov | Bästa struktur | Nyckelkostnad |
|---|---|---|
| Slumpmässig åtkomst efter index | dynamic array | O(1) |
| Sökning efter nyckel | hash map | O(1) genomsnitt |
| Sorterad + områdesfrågor | balanced BST | O(log n) |
| Min/max upprepade gånger | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Prefixsökning | trie | O(L) |

## Exempel på resonemang

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

## Varför det är viktigt

Rätt val är ofta skillnaden mellan en O(n) och en O(n²) lösning — den enskilt viktigaste hävstången för prestanda.

Interviuarna testar just detta resonemang: de vill se att du mappar operationer till deras kostnader, inte att du bara memorerar strukturer.

Behov	Bästa struktur	Nyckelkostnad
Slumpmässig åtkomst efter index	dynamic array	O(1)
Sökning efter nyckel	hash map	O(1) genomsnitt
Sorterad + områdesfrågor	balanced BST	O(log n)
Min/max upprepade gånger	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Prefixsökning	trie	O(L)