Wie wählen Sie die richtige Datenstruktur für ein Problem aus?

Question

Accepted Answer

Wählen Sie die Struktur, deren **häufigste Operationen für Ihr Zugriffsmuster am günstigsten sind**. Beginnen Sie damit, die Operationen aufzulisten, die Sie ausführen werden, schätzen Sie deren Häufigkeit, und ordnen Sie sie dann den Stärken der Struktur zu.

## Warum es wichtig ist

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

## Operationen der Komplexität zuordnen

| Bedarf | Beste Struktur | Kosten der Schlüsseloperation |
|---|---|---|
| Zufallszugriff nach Index | dynamic array | O(1) |
| Suche nach Schlüssel | hash map | O(1) avg |
| Sortiert + Bereichsabfragen | balanced BST | O(log n) |
| Min/Max wiederholt | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Präfixsuche | trie | O(L) |

## Beispielüberlegung

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

## Warum es wichtig ist

Die richtige Wahl ist oft der Unterschied zwischen einer O(n)- und einer O(n²)-Lösung — der größte Leistungshebel.

Interviewer testen genau diese Argumentation: Sie möchten sehen, wie Sie Anforderungen auf Operationskosten abbilden, nicht einfach Strukturen auswendig lernen.

Bedarf	Beste Struktur	Kosten der Schlüsseloperation
Zufallszugriff nach Index	dynamic array	O(1)
Suche nach Schlüssel	hash map	O(1) avg
Sortiert + Bereichsabfragen	balanced BST	O(log n)
Min/Max wiederholt	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Präfixsuche	trie	O(L)