Zum Hauptinhalt springen

Die richtige Datenstruktur wählen

Ein umfassender Leitfaden zur Auswahl der optimalen Datenstruktur für Ihren Anwendungsfall.

Schneller Entscheidungsbaum​

Benötigen Sie Key-Value-Mapping?
├─ Ja → Benötigen Sie sortierte Reihenfolge?
│  ├─ Ja → SortedMap
│  └─ Nein → Benötigen Sie bidirektionale Suche?
│     ├─ Ja → BiDirectionalMap
│     └─ Nein → JavaScript Map (nativ)
│
└─ Nein → Benötigen Sie geordnete Sammlung?
   ├─ Prioritätsbasiert → PriorityQueue / BinaryHeap
   ├─ FIFO (Queue) → Queue
   ├─ LIFO (Stack) → Array oder Deque
   ├─ Beide Enden → Deque
   ├─ Sortierte eindeutige Werte → RedBlackTree
   ├─ String-Präfix-Suche → Trie
   ├─ Sequentieller Zugriff → LinkedList / DoublyLinkedList
   └─ LRU-Caching → LRUCache

Nach Anwendungsfall​

Caching​

AnforderungBeste WahlWarum
Cache fester GrößeLRUCacheAutomatische Entfernung der am wenigsten genutzten
Einfacher CacheJavaScript MapNativ, schnell, keine Größenbeschränkung
Mit TTLLRUCache (mit ttl-Option)Integrierter Ablauf
Multi-Level CacheLRUCache + MapSchnellen und langsamen Speicher schichten

Beispiel:

const cache = new LRUCache<string, Data>({
  capacity: 100,
  ttl: 300000, // 5 Minuten
});

Sammlungen​

Lineare Sammlungen​

BedarfBeste WahlZeitkomplexität
Am Anfang hinzufügen/entfernenLinkedListO(1)
Am Ende hinzufügen/entfernenLinkedList, ArrayO(1)
An beiden Enden hinzufügen/entfernenDoublyLinkedList oder DequeO(1)
Zufälliger Zugriff per IndexArrayO(1)
Sequentielle IterationLinkedList, DoublyLinkedListO(n)
Rückwärts-IterationDoublyLinkedListO(n)

Wann LinkedList vs. Array verwenden:

// ✅ LinkedList verwenden, wenn:
// - Häufige Einfügungen/Löschungen an Enden
// - Größe ändert sich häufig
// - Kein Zufallszugriff erforderlich
const taskQueue = new LinkedList<Task>();

// ✅ Array verwenden, wenn:
// - Zufallszugriff erforderlich (arr[i])
// - Größe relativ stabil
// - Häufige indexbasierte Operationen
const items = [1, 2, 3];

Queue-Operationen​

MusterBeste WahlOperationen
FIFO (First-In-First-Out)Queueenqueue(), dequeue()
LIFO (Last-In-First-Out)Array (als Stack)push(), pop()
PrioritätsbasiertPriorityQueueenqueue(), dequeue() nach Priorität
Beide EndenDequeaddFirst(), addLast(), removeFirst(), removeLast()

Beispielszenarien:

// Task-Verarbeitung (FIFO)
const tasks = new Queue<Task>();

// Rückgängig/Wiederherstellen (LIFO)
const undoStack: Action[] = [];

// Event-Behandlung nach Priorität
const events = new PriorityQueue<Event>({
  comparator: (a, b) => a.priority - b.priority,
});

// Sliding Window
const window = new Deque<number>();

Maps und Lookups​

AnforderungBeste WahlSuchzeit
Key→Value-SucheJavaScript MapO(1) durchschnittl.
Key→Value UND Value→KeyBiDirectionalMapO(1)
Nach Schlüssel sortiertSortedMapO(log n)
Min/Max-SchlüsselzugriffSortedMapO(log n)
Präfixbasierte String-SucheTrieO(m), m=Schlüssellänge

Vergleich:

// Standard-Map
const map = new Map<string, number>();
map.set('a', 1);
map.get('a'); // O(1)

// Bidirektionale Map
const biMap = new BiDirectionalMap<string, number>();
biMap.set('a', 1);
biMap.get('a'); // O(1) - Wert nach Schlüssel abrufen
biMap.getKey(1); // O(1) - Schlüssel nach Wert abrufen

// Sortierte Map
const sorted = new SortedMap<number, string>();
sorted.set(3, 'drei');
sorted.set(1, 'eins');
sorted.firstKey(); // 1 - O(log n)
for (const [k, v] of sorted) {
  // Iteriert in sortierter Reihenfolge
}

// Trie für Strings
const trie = new Trie<number>();
trie.insert('apple', 1);
trie.getAllWithPrefix('app'); // ['apple'] - O(p+n)

Sets und eindeutige Werte​

AnforderungBeste WahlHinweise
Eindeutige Werte, unsortiertJavaScript SetNativ, schnell
Eindeutige Werte, sortiertRedBlackTreeO(log n) Operationen
Min/Max-ZugriffRedBlackTreeO(log n)
Duplikat-PrüfungSet oder RedBlackTreeO(1) oder O(log n)
// Unsortierte eindeutige Werte
const uniqueIds = new Set<string>();

// Sortierte eindeutige Werte
const sortedScores = new RedBlackTree<number>();
sortedScores.insert(85);
sortedScores.insert(92);
sortedScores.min(); // 85
sortedScores.max(); // 92

Tree-Operationen​

BedarfBeste WahlOperationen
Sortierte SammlungRedBlackTreeinsert(), remove(), contains() alle O(log n)
Priority QueuePriorityQueue / BinaryHeapEffizienter Min/Max-Zugriff
String-SucheTriePräfix-Matching, Autocomplete

Prioritäts- und Heap-Operationen​

AnwendungsfallBeste WahlWarum
Task-SchedulingPriorityQueueQueue-ähnliche API mit Prioritäten
K größte/kleinsteBinaryHeap (MinHeap/MaxHeap)Effiziente Top-k-Algorithmen
Median-TrackingMinHeap + MaxHeapZwei-Heap-Ansatz
Dijkstra's AlgorithmusPriorityQueueBenötigt Min-Prioritäts-Extraktion
// Task-Scheduling
const scheduler = new PriorityQueue<Task>({
  comparator: (a, b) => b.priority - a.priority,
});

// K größte Elemente
const minHeap = new MinHeap<number>();
for (const num of numbers) {
  minHeap.insert(num);
  if (minHeap.size > k) minHeap.remove();
}

Leistungsvergleich​

Zeitkomplexität​

DatenstrukturInsertDeleteSearchAccessMin/Max
ArrayO(n)O(n)O(n)O(1)O(n)
LinkedListO(1)*O(n)O(n)O(n)O(n)
DoublyLinkedListO(1)*O(n)O(n)O(n)O(n)
QueueO(1)O(1)O(n)--
DequeO(1)O(1)O(n)O(1)-
PriorityQueueO(log n)O(log n)O(n)O(1)**O(1)**
BinaryHeapO(log n)O(log n)O(n)O(1)**O(1)**
RedBlackTreeO(log n)O(log n)O(log n)-O(log n)
SortedMapO(log n)O(log n)O(log n)-O(log n)
TrieO(m)***O(m)***O(m)***--
BiMapO(1)O(1)O(1)O(1)-
LRUCacheO(1)O(1)-O(1)-

* Nur an Enden ** Peek-Operation *** m = String-Länge

Speicherkomplexität​

DatenstrukturSpeicherHinweise
AlleO(n)Linear in Anzahl der Elemente
LinkedListO(n)Zusätzlicher Zeiger pro Knoten
DoublyLinkedListO(n)Zwei Zeiger pro Knoten
TrieO(ALPHABET_SIZE × N × M)Kann groß sein für lange Strings
BiMapO(2n)Zwei interne Maps

Gängige Szenarien​

1. Webbrowser-Verlauf​

Anforderung: Rückwärts/vorwärts durch besuchte Seiten navigieren

Beste Wahl: DoublyLinkedList

const history = new DoublyLinkedList<string>();
history.append('/home');
history.append('/products');
// Navigieren mit Vorwärts-/Rückwärts-Iteration

Alternative: Array mit Index-Zeiger (einfacher, aber weniger effizient für Änderungen)

2. Autocomplete/Suchvorschläge​

Anforderung: Alle Wörter finden, die mit einem Präfix beginnen

Beste Wahl: Trie

const trie = new Trie<number>(false); // Groß-/Kleinschreibung ignorieren
trie.insert('apple', 100);
trie.insert('application', 85);
trie.getAllWithPrefix('app'); // ['apple', 'application']

Alternative: Array mit Filter (einfacher, aber O(n) pro Suche)

3. Rangliste​

Anforderung: Spielerbewertungen in Rangreihenfolge pflegen

Beste Wahl: SortedMap

const leaderboard = new SortedMap<number, Player>({
  comparator: (a, b) => b - a, // Absteigend
});

Alternative: Array + Sortieren (einfacher, aber O(n log n) pro Aktualisierung)

4. Rate Limiting​

Anforderung: Anfragezähler pro Benutzer mit Ablauf verfolgen

Beste Wahl: LRUCache mit TTL

const rateLimiter = new LRUCache<string, number>({
  capacity: 10000,
  ttl: 60000, // 1 Minute
});

5. Event-Verarbeitung​

Anforderung: Events in Prioritätsreihenfolge verarbeiten

Beste Wahl: PriorityQueue

const events = new PriorityQueue<Event>({
  comparator: (a, b) => a.priority - b.priority,
});

6. Benutzer-ID ↔ Benutzername-Mapping​

Anforderung: In beide Richtungen nachschlagen

Beste Wahl: BiDirectionalMap

const users = new BiDirectionalMap<number, string>();
users.set(1, 'alice');
users.get(1); // 'alice'
users.getKey('alice'); // 1

Entscheidungsfaktoren​

1. Zugriffsmuster​

  • Zufälliger Zugriff: Array, Map
  • Sequentiell: LinkedList, Queue
  • Sortiert: RedBlackTree, SortedMap
  • Priorität: PriorityQueue, BinaryHeap

2. Änderungshäufigkeit​

  • Häufige Einfügungen/Löschungen: LinkedList, Heap
  • Hauptsächlich Lesevorgänge: Array, Map
  • Ausgewogen: Tree-Strukturen

3. Größenbeschränkungen​

  • Feste Größe: LRUCache
  • Dynamische Größe: Die meisten Strukturen
  • Große Datensätze: Speicher-Overhead beachten

4. Leistungsanforderungen​

  • Konstante Zeit kritisch: Map, BiMap, LRUCache
  • Logarithmisch akzeptabel: Trees, Heaps
  • Linear akzeptabel: LinkedList-Suche

Anti-Muster​

❌ Array für häufige Einfügungen/Löschungen verwenden​

// Schlecht: O(n) für jede Verschiebung
const arr = [1, 2, 3];
arr.unshift(0); // Verschiebt alle Elemente

// Gut: O(1)
const list = new LinkedList<number>();
list.prepend(0);

❌ LinkedList für Zufallszugriff verwenden​

// Schlecht: O(n) um Index zu finden
list.get(1000);

// Gut: O(1)
arr[1000];

❌ LRUCache für Caching nicht verwenden​

// Schlecht: Keine automatische Entfernung
const cache = new Map<string, Data>();
if (cache.size > 100) {
  // Manuelle Entfernungslogik erforderlich
}

// Gut: Automatische LRU-Entfernung
const cache = new LRUCache<string, Data>({ capacity: 100 });

Zusammenfassung​

Wählen Sie basierend auf Ihrer primären Operation:

  • Caching: LRUCache
  • FIFO/LIFO: Queue / Stack (Array)
  • Priorität: PriorityQueue
  • Sortiert: RedBlackTree, SortedMap
  • Bidirektionale Suche: BiDirectionalMap
  • String-Präfix: Trie
  • Sequentiell: LinkedList
  • Beide Enden: Deque / DoublyLinkedList

Im Zweifelsfall einfach starten (Array, Map) und basierend auf Profiling optimieren!

Verwandte Themen​