Java Collection und Abstrakte Datentypen

Ein abstrakter Datentyp wird über seine verfügbaren Operationen (Schnittstelle) und deren Verhalten definiert, während die Implementierung und die genutzte Datenstruktur offengelassen werden.[Anhang]

Zu einem ADT existieren regelmäßig mehrere Implementierungen, die dieselbe Schnittstelle mit unterschiedlichen Datenstrukturen und unterschiedlichen Eigenschaften (z.B. Laufzeitkomplexität) realisieren.[Anhang]

Beispiel: Der ADT “List” definiert Operationen wie add(), get(index), remove(), aber nicht WIE diese intern umgesetzt werden. ArrayList nutzt ein Array (schneller Zugriff O(1)), LinkedList nutzt verkettete Knoten (schnelles Einfügen/Löschen am Anfang).[Anhang]

Typische abstrakte Datentypen sind:

• Set (Menge) - keine Duplikate

• List (Liste) - geordnete Sammlung mit Indexzugriff

• Queue (Warteschlange) - FIFO-Prinzip

• Map (Verzeichnis) - Schlüssel-Wert-Zuordnungen[Anhang]

Beispiel: Eine Queue könnte als LinkedList oder als ArrayDeque implementiert werden. Beide bieten die Queue-Operationen (add, poll, peek), aber mit unterschiedlichen Performance-Charakteristiken.[Anhang]

Das Java Collections Framework besteht aus:

• Sammlung (Hierarchie) von abstrakten Datentypen als Java-Interfaces

• Zu jedem ADT mehrere Implementierungen in Form konkreter Klassen

• Vorimplementierte Algorithmen (z.B. zum Sortieren)

• Iterator-Konzept[Anhang]

Beispiel: Das Interface List wird von ArrayList, LinkedList, Vector implementiert. Alle bieten die List-Operationen, aber mit unterschiedlichen Laufzeiten. Collections.sort() ist ein vorimplementierter Algorithmus.[Anhang]

Collection ist der Wurzeltyp (kleinster gemeinsamer Nenner) für die Hierarchie von ADT und bietet nur wenige, sehr einfache Operationen wie size(), isEmpty(), contains(), add(), remove().[Anhang]

Die Spezifikation ist bewusst weit gefasst, um viele unterschiedliche ADT unter sich versammeln zu können (z.B. offen bezüglich Dubletten, Reihenfolge, Nullreferenzen).[Anhang]

Beispiel: Sowohl Set (keine Dubletten) als auch List (Dubletten erlaubt) erweitern Collection, weil Collection selbst keine Festlegung zu Dubletten trifft.[Anhang]

Map ist kein Untertyp von Collection, weil Map Schlüssel-Wert-Paare verwaltet und nicht einzelne Elemente.[Anhang]

Allerdings bietet Map drei sogenannte Collection-Views für den Zugriff: Schlüssel (keySet()), Werte (values()) und Zuordnungen als Schlüssel-Wert-Paare (entrySet()).[Anhang]

Beispiel: Bei `Map<String, Integer> map` liefert `map.keySet()` ein `Set<String>`, `map.values()` eine `Collection<Integer>` und `map.entrySet()` ein `Set<Entry<String,Integer>>`.[Anhang]

Collection bietet:

• Zustandsbeobachtende Operationen: size(), isEmpty(), contains()

• Optional zustandsverändernde Operationen: add(), remove()

• Keine dedizierten Operationen für Elementzugriff, aber Möglichkeit einen Iterator zu erzeugen[Anhang]

Beispiel: `collection.add(element)` kann je nach Implementierung unterschiedliches Verhalten zeigen - bei Set wird ein Duplikat ignoriert, bei List wird es hinzugefügt.[Anhang]

Ein Iterator ist ein Objekt, das die Elemente eines Aggregats sequentiell zur Verfügung stellt, sodass jedes Element genau einmal beobachtet wird.[Anhang]

Das Interface Iterator bietet zwei Hauptoperationen:

• hasNext() - Prüfung, ob ein weiteres Element verfügbar ist

• next() - Abruf des nächsten Elements und internes Weitersetzen[Anhang]

Beispiel:

Iterator<String> it = list.iterator();

while (it.hasNext()) {

String element = it.next();

System.out.println(element);

}

Es ist ein zweiteiliges Konzept:

• Iterable ist ein Interface, das implementiert wird (z.B. von Collection), um Iteratoren erzeugen zu können (per Methode iterator())

• Iterator ist das Interface für die tatsächliche Iteration mit hasNext() und next()[Anhang]

Beispiel: Collection implementiert Iterable. Wenn du `collection.iterator()` aufrufst, erhältst du ein Iterator-Objekt, mit dem du dann über die Elemente iterieren kannst.[Anhang]

Java-Iteratoren dienen hauptsächlich der Traversierung. Die einzige unterstützte Zustandsänderung ist das Entfernen des jeweils zuletzt beobachteten Elements aus der Quelle des Iterators via remove(), und diese Operation ist optional.

Beispiel:

Iterator<String> it = list.iterator();

while (it.hasNext()) {

String element = it.next();

if (element.equals("delete")) {

it.remove(); // löscht das Element aus der Liste

}

}

Iterable-Implementierungen können in erweiterten for-Schleifen (enhanced for loop / for-each) verwendet werden.

Beispiel:

List<String> list = new ArrayList<>();

for (String element : list) { // funktioniert weil List Iterable ist

System.out.println(element);

}

HashMap.get() hat eine durchschnittliche Laufzeitkomplexität von O(1) (amortisiert konstant).

Beispiel: Im Codebeispiel mit `Map<Integer,Integer> m = new HashMap<>()` ist `m.get(value)` in O(1), auch wenn die Map N Einträge hat.

ArrayList.get(index) hat eine Laufzeitkomplexität von O(1), da ArrayList intern ein Array nutzt und direkter Indexzugriff möglich ist.[Anhang]

Beispiel: Im Codebeispiel `input.get(idx)` ist O(1), unabhängig von der Größe der ArrayList.

TreeSet.add() hat eine Laufzeitkomplexität von O(log N), weil TreeSet intern als balancierter Baum (Red-Black-Tree) implementiert ist.

Beispiel: Im Codebeispiel `output.add(result)` mit `TreeSet<Integer> output = new TreeSet<>()` kostet jedes Einfügen O(log N), wobei N die Größe des TreeSet ist.

Wenn die äußere Schleife N-mal läuft und in jeder Iteration eine Operation mit O(log N) ausgeführt wird (z.B. TreeSet.add()), summiert sich das zu O(N log N).

Beispiel:

for(Integer value : input) { // N Iterationen

// ... Berechnungen in O(1) ...

output.add(result); // TreeSet.add() ist O(log N)

}

Gesamt: N × O(log N) = O(N log N)

ArrayList sollte man wählen, wenn häufiger Lesezugriff per Index benötigt wird (O(1)) und Einfügen/Löschen hauptsächlich am Ende stattfindet.[Anhang]

Beispiel: Für Positionsverwaltung `List<Position> positionen = new ArrayList<>()`, wo Positionen der Reihe nach hinzugefügt werden und über Index 0 bis N-1 zugegriffen wird.

LinkedList sollte man wählen, wenn häufiges Einfügen/Löschen am Anfang oder in der Mitte erfolgt, oder wenn Queue-/Deque-Operationen benötigt werden.

Beispiel:

Für FIFO-Queue `Queue<Integer> auftrag = new LinkedList<>()`, wo poll() am Anfang und add() am Ende in O(1) erfolgen.

HashMap sollte man wählen, wenn schnelles Nachschlagen von Schlüssel-Wert-Zuordnungen benötigt wird (O(1)) und die Reihenfolge keine Rolle spielt.[Anhang]

Beispiel: Für Artikelverwaltung `Map<Integer,Artikel> artdb = new HashMap<>()`, um über Artikelnummer (Schlüssel) schnell auf Artikel-Objekte (Wert) zuzugreifen.

TreeSet sollte man wählen, wenn Elemente automatisch sortiert gehalten werden sollen und keine Duplikate erlaubt sind. Operationen sind O(log N).[Anhang]

Beispiel: Für sortierte, eindeutige Ausgabe `Set<Integer> output = new TreeSet<>()` - Elemente werden automatisch aufsteigend sortiert gehalten.

TreeMap: Elemente werden nach natürlicher Ordnung oder Comparator sortiert, get/put sind O(log N).[Anhang]

LinkedHashMap: Elemente behalten Einfügereihenfolge, get/put sind O(1).[Anhang]

Beispiel: Wenn häufige Lesezugriffe wichtiger sind als gelegentliche Änderungen, ist LinkedHashMap besser - Iteration in Einfügereihenfolge bei O(1)-Zugriff statt O(log N) bei TreeMap.

PriorityQueue sollte man verwenden, wenn Elemente nach Priorität verarbeitet werden sollen - das Element mit höchster Priorität wird immer zuerst entnommen.

Beispiel:

Queue<Auftrag> s = new PriorityQueue<>();

Aufträge werden nach Priorität sortiert, poll() liefert immer den Auftrag mit höchster Priorität. Die Auftrag-Klasse muss Comparable implementieren oder ein Comparator übergeben werden.

Beide halten Elemente sortiert, aber:

• TreeSet: Set-Semantik (keine Duplikate), bietet auch sortierte Iteration

• PriorityQueue: Queue-Semantik (FIFO mit Priorität), optimiert für poll() (höchste Priorität zuerst)[Anhang]

Beispiel: Für Auftragsverwaltung nach Priorität sind beide möglich:

Beispiel:

SortedSet<Auftrag> s = new TreeSet<>(); // oder

Queue<Auftrag> s = new PriorityQueue<>();

Amortisiert O(1)” bedeutet, dass einzelne add()-Operationen gelegentlich teurer sein können (beim Vergrößern des internen Arrays), aber über viele Operationen gemittelt konstante Zeit O(1) resultiert.[Anhang]

Beispiel: ArrayList vergrößert ihr Array, wenn es voll ist (z.B. Verdopplung). Das Kopieren ist O(N), passiert aber selten. Über N add()-Operationen ergibt sich durchschnittlich O(1) pro Operation.

LinkedHashSet kombiniert Set-Eigenschaften (keine Duplikate) mit Erhalt der Einfügereihenfolge bei O(1)-Operationen - besser als TreeSet’s O(log N), wenn Ordnung durch Einfügereihenfolge ausreicht.[Anhang]

Beispiel: Für Berechtigungen, die einmalig in sortierter Reihenfolge eingefügt werden und dann oft abgefragt werden:

LinkedHashSet<String> perms = new LinkedHashSet<>();

O(1) für contains() statt O(log N) bei TreeSet, Iteration in Einfügereihenfolge.

poll() entfernt und liefert das erste Element. Bei LinkedList ist dies O(1), weil nur die Referenz am Kopf der Liste angepasst werden muss, ohne Elemente zu verschieben.

Queue<Integer> auftrag = new LinkedList<>();

Integer artnum = auftrag.poll(); // O(1) am Anfang

Im Gegensatz dazu wäre poll() bei ArrayList als Queue ineffizient (O(N)), weil alle Elemente verschoben werden müssten.

Weil schneller Zugriff auf Artikel über Artikelnummer (eindeutiger Schlüssel) benötigt wird - HashMap bietet O(1) für get().

Map<Integer,Artikel> artdb = new HashMap<>();

Artikel art = artdb.get(artikelnummer); // O(1)

Die Reihenfolge der Artikel spielt keine Rolle, daher keine TreeMap nötig.

List<Position> ermöglicht Zugriff per Index (Positionsnummer) in O(1), während Map<Artikel,Position> schnelles Prüfen “existiert Position für diesen Artikel?” in O(1) ermöglicht.

List<Position> positionen = new ArrayList<>(); // für Indexzugriff

Map<Artikel,Position> arttopos = new HashMap<>(); // für schnelle Suche

Beide Strukturen halten Referenzen auf dieselben Position-Objekte.

Wenn häufige Änderungen vorkommen und Elemente dabei automatisch sortiert bleiben sollen. TreeMap/TreeSet halten Ordnung dynamisch bei.[Anhang]

Beispiel: Wenn Berechtigungen häufig hinzugefügt/entfernt werden und immer sortiert verarbeitet werden sollen, ist TreeMap besser - jede Operation O(log N), aber keine teure Neustrukturierung.

Wenn Änderungen selten sind, aber Lesezugriffe häufig. LinkedHashMap/LinkedHashSet bieten O(1) statt O(log N), wenn Elemente einmalig sortiert eingefügt werden.

Beispiel: Im Berechtigungs-Beispiel sind Änderungen selten - man fügt Berechtigungen einmalig in sortierter Reihenfolge ein, dann häufig O(1)-Zugriff mit contains(). Änderungen erfordern Neuaufbau O(N), aber das ist selten.

Man optimiert für den häufigen Fall (z.B. Lesezugriff O(1) statt O(log N)) und nimmt dafür schlechtere Laufzeit beim seltenen Fall (z.B. Änderungen O(N) statt O(log N)) in Kauf.

Beispiel: LinkedHashMap/LinkedHashSet für vorsortierten, selten geänderten Zustand:

• Häufig: contains() in O(1) (statt O(log N) bei Tree-Varianten)

• Selten: Neuaufbau bei Änderung in O(N) (statt O(log N) pro Änderung)

Das lohnt sich, wenn Lesezugriffe >> Schreibzugriffe.