Auswahl-Cheatsheet
Wie wählt man die richtige Datenstruktur? Hier eine Entscheidungs-Hilfe nach typischen Anwendungen:
| Anwendung | Empfohlene Struktur | Warum |
|---|---|---|
| Reihenfolge wichtig, häufiger Index-Zugriff | Array | O(1) Zugriff, Cache-Lokalität |
| Lookup per Schlüssel (User-ID → User) | Hash-Map | O(1) Lookup |
| Deduplizieren von Werten | Set | O(1) Has-Check |
| Undo-History, Funktions-Aufrufe | Stack | LIFO |
| Job-Verarbeitung in Reihenfolge | Queue | FIFO |
| "Wichtigster zuerst" (Job-Scheduler, Dijkstra) | Priority Queue / Heap | O(log n) extract-min |
| Sortierte Daten + häufiger Lookup | Sortiertes Array oder Balanced Tree | Binary Search O(log n) |
| Range-Queries ("Alter zwischen 20-30") | Balanced Tree (TreeMap) | Sortierte Reihenfolge |
| Autovervollständigung | Trie | Präfix-Suche O(L) |
| DB-Index | B-Tree / B+Tree | Optimiert für Plattenzugriffe |
| Cache mit Eviction | Hash-Map + Linked List (LRU) | O(1) Lookup + O(1) Eviction |
| Graph-Daten | Adjacency List (Map → Array) | Sparse Graphs |
Faustregel
"Was muss schnell sein?" → wähle die Datenstruktur, die DIESE Operation in O(1) oder O(log n) macht. Andere Operationen darfst du opfern.
Zurück zu Informatik