Liste • Datenstrukturen

Spezialisierte lineare Datenstrukturen

Doppelt verkettete Listen
• Beschreibung: Jeder Knoten enthält neben den Daten zwei Zeiger (vorheriger/nächster Knoten).
• Vorteile: Effizientes Einfügen/Löschen an beiden Enden (O(1)).
• Anwendung: Browser-Verlauf (Vor/Zurück-Navigation).

Zirkuläre Puffer (Ringbuffer)
• Beschreibung: Ein Array mit fixer Größe, bei dem das Ende wieder an den Anfang „gebunden“ ist.
• Vorteile: Konstanter Speicherverbrauch, ideal für Echtzeit-Datenströme.
• Anwendung: Audio-/Video-Pufferung (z. B. MP3-Player).

Deque (Double-Ended Queue)
• Beschreibung: Eine Warteschlange, die Einfügen/Löschen an beiden Enden erlaubt.
• Vorteile: Flexibler als Stacks/Queues (O(1) für alle End-Operationen).
• Implementierung: Oft als dynamisches Array oder doppelt verkettete Liste.

Fortgeschrittene Baumstrukturen

AVL-Bäume & Rot-Schwarz-Bäume
• Beschreibung: Selbstbalanciierende Binärbäume, die degenerierte (unbalancierte) Bäume vermeiden.
• Vorteile: Garantierte O(log n) für Suchen/Einfügen/Löschen.
• Anwendung: Datenbank-Indizes (z. B. in Java’s TreeMap).

B-Bäume & B+-Bäume
• Beschreibung: Balancierte Mehrweg-Suchbäume mit hohem Verzweigungsgrad.
• Vorteile: Optimiert für Festplattenzugriffe (Block-basierte Speicherung).
• Anwendung: Dateisysteme (ext4, NTFS), Datenbanken (MySQL, PostgreSQL).

Trie (Präfixbaum)
• Beschreibung: Baum zur Speicherung von Zeichenketten, wobei Pfade Wörtern entsprechen.
• Vorteile: Schnelle Präfixsuche (O(k) für ein Wort der Länge k).
• Anwendung: Autovervollständigung (Suchmaschinen), Rechtschreibprüfung.

Heap (Priority Queue)
• Beschreibung: Binärbaum, bei dem jeder Knoten größer/kleiner als seine Kinder ist (Min-/Max-Heap).
• Vorteile: Effizientes Entfernen des Extremwerts (O(log n)).
• Anwendung: Dijkstra-Algorithmus, Task-Scheduling.

Raumbezogene Datenstrukturen

Für geometrische Daten oder räumliche Abfragen:

Quadtree & Octree
• Beschreibung: Hierarchische Unterteilung von 2D-/3D-Räumen in Quadranten/Oktanten.
• Anwendung: Kollisionserkennung in Spielen, GIS (Google Maps).

R-Baum
• Beschreibung: Balancierter Baum für mehrdimensionale Daten (z. B. Geo-Koordinaten).
• Anwendung: Datenbanken für räumliche Abfragen (PostGIS).

k-d-Baum
• Beschreibung: Binärbaum zur Partitionierung von k-dimensionalen Räumen.
• Anwendung: Maschinelles Lernen (nearest-neighbor-Suche).

Probabilistische Datenstrukturen

Für approximative Abfragen mit minimalem Speicherbedarf:

Bloom-Filter
• Beschreibung: Bit-Array mit Hash-Funktionen zur Mengenmitgliedschaftsprüfung.
• Vorteile: Speichereffizient (keine false negatives, aber false positives).
• Anwendung: Web-Caching (Vermeidung teurer Datenbankabfragen).

HyperLogLog
• Beschreibung: Schätzt die Kardinalität großer Mengen mit konstantem Speicher.
• Anwendung: Unique Visitors-Analyse (z. B. bei Twitter).

Zeitbasierte Datenstrukturen

Für zeitliche Abfolgen oder Ereignisverwaltung:

Skip-Liste
• Beschreibung: Hierarchisch verkettete Liste mit „Express-Spuren“ für O(log n)-Suche.
• Vorteile: Einfacher zu implementieren als balancierte Bäume.
• Anwendung: Redis-Datenbank.

Segment-Baum
• Beschreibung: Baum zur effizienten Bereichsabfrage (Range Queries).
• Anwendung: Statistische Analysen (z. B. Maximum/Minimum in einem Intervall).

Die optimale Wahl hängt von den Anforderungen ab:

Anforderung	Empfohlene Struktur
Schnelle Suche	Hash-Tabelle, AVL-Baum
Dynamische Größe	Verkettete Liste, B-Baum
Räumliche Abfragen	Quadtree, R-Baum
Echtzeit-Datenströme	Ringbuffer, Heap
Speichereffizienz	Bloom-Filter, Bit-Vector