Collections-Framework (List, Set, Map)

Du brauchst eine Datenstruktur, deren Größe sich zur Laufzeit ändert? Das Java-Collections-Framework liefert dir dafür 3 große Familien: List (geordnete Reihenfolge, Duplikate erlaubt), Set (keine Duplikate), Map (Key-Value-Zuordnung). Sie sind das Brot-und-Butter-Werkzeug in jedem Java-Programm, vom Warenkorb über eindeutige Tags bis zum Telefonbuch. Die richtige Wahl zwischen List, Set und Map ist nicht nur Stil: sie entscheidet, ob unerwünschte Duplikate entstehen, ob eine Suche in O(1) oder O(n) läuft, und ob deine Reihenfolge erhalten bleibt. Genau deshalb ist sie in Klausuren und in echtem Code so zentral. Du lernst hier die drei Familien, ihre wichtigsten Operationen, die Default-Implementierungen ArrayList / HashSet / HashMap, die sortierten Tree-Varianten und die typischen Klausur-Fallen (Index auf Set, null in TreeMap, equals/hashCode bei eigenen Klassen, ConcurrentModificationException).

Typische Klausurfrage: "Wann List, wann Set, wann Map?" zusammen mit den jeweiligen Operationen.

Big-O kurz: O(1) heißt konstante Zeit, unabhängig von der Größe (gleich schnell bei 10 oder 10 Mio. Elementen). O(log n) wächst langsam mit, O(n) linear (doppelt so viele Elemente, doppelt so lange). Diese drei Klassen reichen für die ganze Collections-Diskussion.

Die Idee in einem Satz

Wähle die Datenstruktur nach deiner Frage: Brauchst du die Reihenfolge? → List. Willst du Duplikate verhindern? → Set. Brauchst du einen Schlüssel-Lookup (Wert unter Schlüssel)? → Map.

Die 3 Familien im Überblick

List  [0]   [1]   [2]   [3]        Zugriff über Index, Reihenfolge fest
      "A"   "B"   "A"   "C"        Duplikate ("A" doppelt) erlaubt

Set   { "A" , "B" , "C" }         kein Index, keine Reihenfolge-Garantie
      add("A") zum 2. Mal -> ignoriert (Filter), Frage: contains?

Map   "Anna" -> 1                 Schlüssel -> Wert, Schlüssel eindeutig
      "Ben"  -> 3                 get("Anna") liefert 1

Visuell ausprobieren: Im Interaktiv-Tab kannst du genau diese drei Strukturen mit identischen Operationen nebeneinander durchspielen, und darunter zerlegen drei Code-Stepper (je einer für List, Set, Map) jede Operation Schritt für Schritt, genau dort setzt die typische Klausur-Tracing-Aufgabe an.

List, die geordnete Liste

Verwende List wenn: du Items in einer bestimmten Reihenfolge speichern willst und Duplikate erlaubt sind.

Index:    0       1       2
        ┌───────┬───────┬───────┐
namen   │ Anna  │  Ben  │ Anna  │   get(1) -> "Ben", Duplikat "Anna" ok
        └───────┴───────┴───────┘

import java.util.ArrayList;
import java.util.List;

List<String> namen = new ArrayList<>();
namen.add("Anna");
namen.add("Ben");
namen.add("Anna");  // Duplikat ist ok

System.out.println(namen);     // [Anna, Ben, Anna]
System.out.println(namen.size());     // 3
System.out.println(namen.get(1));     // Ben
namen.remove(0);
System.out.println(namen);     // [Ben, Anna]

Wichtigste Operationen:

• add(e), hinten anfügen (bei ArrayList amortisiert O(1))
• add(i, e), an Index i einfügen (am Anfang O(n), weil alle folgenden Elemente verschoben werden)
• get(i), Element holen (bei ArrayList O(1), direkter Index-Zugriff)
• set(i, e), Element ersetzen
• remove(i), Element löschen (am Anfang O(n) wegen Verschiebung)
• size(), Anzahl
• contains(e), enthält? (O(n)!)
• indexOf(e), erster Index

Genau hinschauen: Bei ArrayList ist nur der reine Index-Zugriff get(i) konstant (O(1)). Einfügen oder Löschen am Anfang ist O(n), weil dahinter alles eine Position weiterrutschen muss. add(e) ohne Index hängt hinten an und ist deshalb schnell.

Set, die duplikatfreie Sammlung

Verwende Set wenn: du nur prüfen willst, ob etwas vorkommt, und Duplikate egal sind (sollen weg).

add("java")  ──►  ┌─────────────────────┐
add("oop")   ──►  │  { "java" , "oop" }  │   contains("oop")? -> true (O(1))
add("java")  ──►  └─────────────────────┘   2. "java" wird vom Filter
                   Duplikat-Filter             abgewiesen, size bleibt 2

import java.util.HashSet;
import java.util.Set;

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("oop");
tags.add("java");  // Duplikat wird ignoriert!

System.out.println(tags.size());            // 2
System.out.println(tags.contains("oop"));   // true (sehr schnell, O(1))

Wichtigste Operationen:

• add(e), hinzufügen (true wenn neu)
• contains(e), enthält? (O(1) bei HashSet)
• remove(e), entfernen
• size()
• Kein get(i)! Sets haben keinen Index und keinen Key. Du fragst nicht "gib mir Element Nr. 3", sondern "ist Element e drin?" über contains(e) (bei HashSet typischerweise O(1)).

Achtung bei eigenen Klassen: Ob ein Set ein Element als Duplikat erkennt, entscheidet es über equals() und hashCode(). Eigene Klassen (z. B. Student) musst du diese beiden Methoden überschreiben lassen, sonst werden Objekte nur per Referenz verglichen, und zwei Student-Objekte mit gleichem Inhalt landen beide im Set. Mehr dazu unter "Häufige Stolpersteine".

HashSet vs. TreeSet: HashSet ist unsortiert, sehr schnell (durchschnittlich O(1) für add/contains bei guter Hash-Verteilung). TreeSet ist sortiert (alphabetisch / numerisch), aber langsamer (garantiert O(log n)). Ein weiterer Unterschied: HashSet erlaubt ein null-Element, TreeSet mit natürlicher Ordnung (Comparable) wirft beim Einfügen von null eine NullPointerException (es müsste null sortieren, was nicht geht).

Map, die Schlüssel-Wert-Zuordnung

Verwende Map wenn: du Werte unter einem Schlüssel ablegen willst, also das Telefonbuch-Prinzip (Name → Nummer).

        Schlüssel (Key)        Wert (Value)
        ┌───────────┐          ┌───┐
        │  "Anna"   │ ───────► │ 1 │   put("Anna", 2) überschreibt -> 2
        ├───────────┤          ├───┤
        │  "Ben"    │ ───────► │ 3 │   get("Ben") -> 3
        └───────────┘          └───┘
        Keys eindeutig         Werte dürfen sich wiederholen

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> noten = new HashMap<>();
noten.put("Anna", 1);
noten.put("Ben", 3);
noten.put("Anna", 2);  // ersetzt Annas alte Note!

System.out.println(noten.get("Anna"));      // 2
System.out.println(noten.containsKey("Ben")); // true
System.out.println(noten.size());           // 2

Wichtigste Operationen:

• put(k, v), Wert unter Key speichern (überschreibt)
• get(k), Wert holen (null wenn nicht da)
• containsKey(k), Key vorhanden?
• remove(k), Eintrag löschen
• keySet(), alle Keys als Set
• values(), alle Werte als Collection
• entrySet(), alle Key-Value-Paare

Iteration: die for-each-Schleife

// List
for (String name : namen) {
    System.out.println(name);
}

// Set
for (String tag : tags) {
    System.out.println(tag);
}

// Map
for (Map.Entry<String, Integer> eintrag : noten.entrySet()) {
    System.out.println(eintrag.getKey() + " = " + eintrag.getValue());
}

Klausur-Frage: "Was passiert wenn du während des for-each-Loops strukturell Elemente entfernst?" → Das ist unzulässig und löst typischerweise eine ConcurrentModificationException aus. Wichtig: Diese Prüfung ist best-effort, also nicht garantiert. Je nach Position kann derselbe Loop sogar ohne Exception durchlaufen (klassischer Fall: du entfernst das vorletzte Element) und liefert dann still ein falsches Ergebnis, was noch gefährlicher ist als ein Absturz. Merke: Verlass dich nie darauf, dass es kracht, modifiziere einfach nie während des for-each. Lösung: Iterator explizit nutzen oder removeIf(...). Letzteres ist die kürzeste sichere Variante:

// UNZULAESSIG: modifiziert die Liste waehrend des for-each.
// Wirft MEIST eine ConcurrentModificationException, aber best-effort:
// je nach Position kann es auch still durchlaufen (= versteckter Bug).
for (String name : namen) {
    if (name.equals("Ben")) namen.remove(name);
}

// SAFE: removeIf nimmt ein Predicate und entfernt intern korrekt
namen.removeIf(name -> name.equals("Ben"));

Wichtige Implementierungen

ArrayList vs. LinkedList (Klausur-Klassiker): ArrayList ist am Ende schnell und am Anfang langsam (O(n) durch Verschieben), aber get(i) ist O(1). LinkedList ist umgekehrt: schnelles Insert/Remove an Anfang und Ende (O(1)), aber get(i) in der Mitte ist O(n), weil die Liste von vorne durchlaufen werden muss. Im Zweifel ArrayList: der schnelle Index-Zugriff überwiegt fast immer.

Daumenregel: Wenn unsicher → ArrayList, HashSet, HashMap. Die sind 90% aller Fälle die richtige Wahl.

Beispiel: Wann was?

Klausur-Faustregeln

1. List = geordnet + Duplikate. Set = duplikatfrei. Map = Key→Value. Ende.

2. ArrayList ist Default-List. HashMap ist Default-Map. HashSet ist Default-Set. Spezialisierte Implementierungen erst wenn du einen Grund hast.

3. Hash-Implementierungen sind durchschnittlich O(1) für add/contains/get (bei guter Hash-Verteilung; Worst-Case schlechter). Tree-Implementierungen sind O(log n). Listen sind O(n) für contains.

4. null als Wert/Key, genau differenzieren:

• HashSet erlaubt ein null-Element (mehr nicht, ist ja duplikatfrei).
• HashMap erlaubt einen null-Key und beliebig viele null-Values (mehrere Keys dürfen auf null zeigen).
• TreeSet / TreeMap mit natürlicher Ordnung (Comparable) werfen beim Einfügen von null (Element bzw. Key) eine NullPointerException, weil null nicht sortierbar ist. (Ausnahme: ein eigens geschriebener null-fähiger Comparator, kein Klausur-Standard.)

5. equals und hashCode müssen konsistent sein wenn du eigene Klassen in Sets/Maps speicherst. Sonst tauchen Objekte mehrfach auf oder werden nicht gefunden.

Klausur-Beispielaufgabe

Beispiel (typischer Klausur-Stil, zur Übung konstruiert, keine reale Klausur).

Eine Bibliothek-Anwendung soll drei Daten verwalten. Ordne jeder Anforderung die passende Collection (List, Set oder Map) plus eine konkrete Implementierung zu und begründe kurz:

1. Die Ausleih-Historie eines Nutzers (jedes ausgeliehene Buch, in zeitlicher Reihenfolge, dasselbe Buch darf mehrfach vorkommen).
2. Die Menge der ISBN-Nummern, die aktuell im Bestand sind (jede ISBN höchstens einmal, schnelle "ist X im Bestand?"-Abfrage).
3. Die Zuordnung Nutzer-ID → Nutzer-Objekt für schnellen Zugriff per ID.

Zusatzfrage: Bei einem Bestand von 10.000 ISBNs, welche Laufzeit hat die Abfrage "ist diese ISBN im Bestand?" in deiner Lösung, und wie viele Operationen fallen worst-case an, wenn man stattdessen eine ArrayList verwendet hätte?

Lösungsschritte:

1. Ausleih-Historie → List, konkret ArrayList<Buch>. Begründung: Reihenfolge ist Teil der Information (chronologisch) und Duplikate sind erlaubt (dasselbe Buch mehrfach ausgeliehen). Damit fallen Set (verbietet Duplikate) und Map (braucht Schlüssel) aus. (Deckt der Abschnitt "List, die geordnete Liste".)
2. ISBN-Bestand → Set, konkret HashSet<String>. Begründung: jede ISBN höchstens einmal (Duplikat-Freiheit) und es wird nur "enthält?" gefragt, kein Index und kein Wert nötig. HashSet liefert contains(isbn) in O(1). (Deckt der Abschnitt "Set, die duplikatfreie Sammlung".)
3. Nutzer-ID → Nutzer → Map, konkret HashMap<Integer, Nutzer>. Begründung: klassischer Schlüssel-Lookup, get(id) liefert das Objekt in O(1). (Deckt der Abschnitt "Map, die Schlüssel-Wert-Zuordnung".)
4. Laufzeit der ISBN-Abfrage (bei 10.000 ISBNs): mit HashSet ist contains durchschnittlich O(1), also unabhängig von der Bestandsgröße ungefähr konstant wenige Schritte. Mit einer ArrayList wäre dieselbe Abfrage O(n): worst-case müssen alle 10.000 Einträge durchgegangen werden (das gesuchte Element ganz hinten oder gar nicht vorhanden). Genau dieser Unterschied (konstant vs. bis zu 10.000 Vergleiche) ist die typische Begründung, warum man hier Set statt List nimmt. (Deckt die Abschnitte "Wichtige Implementierungen" und "Klausur-Faustregeln".)

Häufige Stolpersteine

1. Set mit Index zugreifen. set.get(0) gibt's nicht. Wenn du Index brauchst → List.

2. map.get(key) ohne Null-Check. Wenn Key nicht da → null zurück. Ein NullPointerException bei der nächsten Operation ist garantiert. Lösung: containsKey vorher oder getOrDefault.

3. Collections.sort(set) versuchen. Set ist nicht sortiert (ausser TreeSet). sort funktioniert nur auf List. Wenn du eine sortierte Reihenfolge willst: new ArrayList<>(set) und dann sortieren.

4. Eigene Objekte in HashSet/HashMap ohne equals/hashCode override. Standard-equals vergleicht Referenzen, nicht Inhalt. Zwei Student-Objekte mit gleichem Namen sind dann "verschieden". Lösung: equals und hashCode überschreiben.

5. ConcurrentModificationException beim Iterieren + Entfernen. Niemals in einem for-each-Loop collection.remove(...) aufrufen. Lösung: removeIf(predicate) oder expliziter Iterator mit it.remove().

Collections-Vergleichs-Visualizer

3 identische Operationen, ausgeführt auf List, Set, Map gleichzeitig. Beobachte die Unterschiede.

Wähle eine Operation aus und sieh, was bei jeder Datenstruktur passiert. So merkst du dir Reihenfolge / Duplikate / Lookup-Verhalten ohne auswendig zu lernen.

Beispiel-Operationen: add("java"), add("java") (zweites Mal), contains("java"), size(). Achte darauf, wie das Set das zweite "java" abweist (size bleibt 1), die List es brav als Duplikat aufnimmt (size 2), und die Map dafür einen Key braucht statt eines reinen Werts.

Klausur-Tipp: Bei Klausurfragen zur Datenstruktur-Wahl frag dich: (1) Ist die Reihenfolge wichtig? → List. (2) Sind Duplikate ok? Wenn nein → Set. (3) Brauche ich Lookup über einen Schlüssel? → Map. In 90% aller Fälle reicht diese Entscheidungslogik.

---

Code-Stepper: Schritt für Schritt durchspielen

Drei interaktive Demos, je eine pro Familie. Klick Step oder Auto und beobachte, wie sich die Datenstruktur, ihre Größe und die Konsole pro Operation verändern. Genau dieser Verlauf wird in Klausuren als Tracing-Aufgabe abgefragt.

1. List (ArrayList): Reihenfolge bleibt, Duplikate erlaubt

add hängt hinten an, get(1) greift über den Index zu, remove(0) löscht das erste Element und alles rückt nach.

2. Set (HashSet): Duplikat-Filter in Aktion

Das dritte add("java") ist ein Duplikat und wird stillschweigend abgewiesen. size() bleibt deshalb bei 2, und contains ist die typische Set-Frage.

3. Map (HashMap): put überschreibt bei gleichem Key

Der zweite put("Anna", ...) legt keinen neuen Eintrag an, sondern überschreibt Annas Wert, weil Keys eindeutig sind. get auf einen fehlenden Key liefert null.

Collections, Praxis-Übung

6 Aufgaben zur Wahl der richtigen Datenstruktur und ihren Operationen.