datenstrukturen

Data Structures (Datenstrukturen)

Kurz: Ein Oberbegriff für standardisierte Arten, Daten so zu organisieren und zu speichern, dass bestimmte Operationen (Suchen, Einfügen, Sortieren) effizient möglich sind.

Genauer: Die Wahl der richtigen Datenstruktur hat großen Einfluss auf die Performance eines Programms — ein Array ist z. B. schnell im direkten Zugriff über einen Index, aber langsam beim Einfügen in der Mitte; eine verkettete Liste ist umgekehrt. Collections fassen die gängigsten Datenstrukturen (Listen, Mengen, Zuordnungen) in einer gemeinsamen, wiederverwendbaren Bibliothek zusammen.

Im Detail

Der Kerngedanke: Es gibt keine “beste” Datenstruktur — jede macht einen bewussten Kompromiss zwischen verschiedenen Operationen, und die richtige Wahl hängt davon ab, welche Operation im konkreten Anwendungsfall am häufigsten vorkommt.

                    Zugriff per Index   Einfügen (Mitte)   Suchen (unsortiert)
Array               O(1) schnell         O(n) langsam        O(n)
Verkettete Liste     O(n) langsam         O(1) schnell        O(n)
Hash-Menge/-Map      -                    O(1) schnell        O(1) schnell (Hashing)
Balancierter Baum    -                    O(log n)            O(log n), dazu sortiert

Diese Tabelle zeigt das grundlegende Muster: Eine Struktur, die in einer Spalte glänzt, ist in einer anderen oft besonders schlecht. Ein Array liest schnell, weil die Speicheradresse eines Elements direkt aus seinem Index berechnet werden kann — aber ein Element in der Mitte einzufügen bedeutet, alle nachfolgenden Elemente im Speicher zu verschieben. Eine verkettete Liste verknüpft Elemente stattdessen über Zeiger/Referenzen, wodurch Einfügen blitzschnell wird (nur zwei Zeiger umbiegen), aber der direkte Zugriff auf das n-te Element bedeutet, sich von vorne durchzuhangeln.

Die Auswahl der richtigen Datenstruktur beginnt deshalb immer mit der Frage: “Welche Operation führe ich am häufigsten aus?”

• Häufig per Index/Schlüssel zugreifen, selten einfügen → Array oder Hash-Map.
• Häufig am Anfang/Ende einfügen oder entfernen, selten wahlfrei zugreifen → verkettete Liste, Queue oder Stack.
• Häufig auf Duplikate prüfen oder Mitgliedschaft testen → Menge (Set).
• Reihenfolge/Sortierung muss erhalten bleiben und effizient durchsuchbar sein → balancierter Baum (z. B. TreeSet/TreeMap).

Ein Datenstruktur-Fehlgriff macht sich meist erst bei wachsenden Datenmengen bemerkbar — bei 100 Elementen ist praktisch jede Struktur “schnell genug”, bei 10 Millionen wird der Unterschied zwischen O(n) und O(log n) oder O(1) zum entscheidenden Faktor, ob ein Programm in Millisekunden oder Minuten antwortet.

Siehe auch: Arrays, Collections, Algorithms