Data Structures

Kurz: Organisierte Formen, Daten im Speicher zu halten — Java stellt über das Collections-Framework fertige Implementierungen für Listen, Mengen und Zuordnungen bereit.

Genauer: Die Wahl der Datenstruktur bestimmt maßgeblich die Performance eines Programms: eine ArrayList erlaubt schnellen Zugriff per Index, eine LinkedList schnelles Einfügen/Entfernen mitten in der Liste, ein HashSet schnelles Prüfen auf Enthaltensein. Java-Arrays (siehe Arrays) sind die einfachste, aber unflexibelste Datenstruktur.

Im Detail

Datenstruktur	Zugriff per Index	Einfügen/Entfernen (Mitte)	Enthalten-Prüfung	Duplikate
ArrayList	O(1) schnell	O(n) langsam	O(n)	erlaubt
LinkedList	O(n) langsam	O(1) schnell (an bekannter Stelle)	O(n)	erlaubt
HashSet	kein Index	O(1) im Schnitt	O(1) im Schnitt	keine
HashMap	Zugriff per Schlüssel O(1)	O(1) im Schnitt	O(1) im Schnitt (Schlüssel)	Schlüssel eindeutig

Diese Tabelle ist der eigentliche Kern der Entscheidung “welche Datenstruktur nehme ich”: Braucht man häufigen Zugriff per Position → ArrayList. Häufiges Einfügen/Entfernen an bekannten Stellen (z. B. eine Warteschlange) → LinkedList oder ArrayDeque. Häufiges “ist X schon enthalten?” ohne Duplikate → HashSet. Zuordnung von Schlüsseln zu Werten (z. B. Name → Telefonnummer) → HashMap. Die O(1)-Werte bei HashSet/HashMap gelten nur im statistischen Durchschnitt — im theoretischen Worst Case (viele Hash-Kollisionen) können sie auf O(n) fallen, was in der Praxis aber sehr selten vorkommt.

Wie HashMap intern O(1) erreicht

Der Grund für den schnellen Zugriff bei HashMap/HashSet liegt in der internen Struktur: Jeder Schlüssel wird über hashCode() auf einen Bucket-Index abgebildet, sodass beim Nachschlagen nicht die komplette Struktur durchsucht werden muss, sondern direkt der passende Bucket angesprungen wird. Kollidieren zwei unterschiedliche Schlüssel im selben Bucket (Hash-Kollision), werden sie dort intern als kleine Liste oder — bei vielen Kollisionen — als Baum verwaltet, was im Extremfall die Performance auf O(log n) statt O(n) begrenzt (seit Java 8).

Eigene Datenstrukturen vs. Standardbibliothek

Fast jeder Anfängerfehler bei Datenstrukturen besteht darin, eine eigene, einfachere Lösung (z. B. ein manuell verwaltetes Array mit eigener “ist voll”-Logik) statt der fertigen Collections-Klassen zu bauen — das kostet unnötig Zeit und ist fehleranfälliger, ohne einen echten Vorteil zu bieten. Eigene Datenstrukturen lohnen sich nur bei sehr speziellen Anforderungen, die keine Standardklasse abdeckt (z. B. eine Prioritätswarteschlange mit dynamisch änderbaren Prioritäten, wofür PriorityQueue nicht direkt ausreicht).

Speicherbedarf als weiterer Faktor

Neben der Zeitkomplexität spielt auch der Speicherbedarf eine Rolle: Ein primitives int[]-Array benötigt deutlich weniger Speicher als eine gleich große ArrayList<Integer>, weil letztere jedes Element als eigenständiges Integer-Objekt mit Objekt-Overhead speichert (Autoboxing). Bei sehr großen Datenmengen kann dieser Unterschied entscheidend sein.

Siehe auch: Collections, Arrays, Algorithms, HashSet