Was ist ein abstrakter Datentyp (ADT)?
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]
Welche typischen abstrakten Datentypen gibt es?
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]
Aus welchen groben Komponenten besteht das Java Collections Framework?
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]
Welche Rolle spielt Collection als Wurzeltyp im Framework?
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]
Warum ist Map kein Untertyp von Collection?
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]
Welche Operationen bietet Collection an?
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]
Was ist ein Iterator und welche Operationen bietet er?
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);
}
Was ist der Unterschied zwischen Iterator und Iterable?
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]
collection.iterator()
Welche Zustandsänderung unterstützen Java-Iteratoren?
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.
if (element.equals("delete")) {
it.remove(); // löscht das Element aus der Liste
Wofür können Iterable-Implementierungen verwendet werden?
Iterable-Implementierungen können in erweiterten for-Schleifen (enhanced for loop / for-each) verwendet werden.
List<String> list = new ArrayList<>();
for (String element : list) { // funktioniert weil List Iterable ist
Was ist die Laufzeitkomplexität von HashMap.get()?
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.
`Map<Integer,Integer> m = new HashMap<>()` ist `m.get(value)`
Was ist die Laufzeitkomplexität von ArrayList.get(index)?
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.
Was ist die Laufzeitkomplexität von TreeSet.add()?
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.
Warum ist die Gesamtkomplexität bei N Iterationen × O(log N) pro Iteration = O(N log N)?
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).
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)
Wann sollte man ArrayList wählen?
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.
Wann sollte man LinkedList wählen?
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.
Für FIFO-Queue `Queue<Integer> auftrag = new LinkedList<>()`, wo poll() am Anfang und add() am Ende in O(1) erfolgen.
Wann sollte man HashMap wählen?
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.
Wann sollte man TreeSet wählen?
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.
Was ist der Unterschied zwischen TreeMap und LinkedHashMap?
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.
Wann sollte man PriorityQueue verwenden?
PriorityQueue sollte man verwenden, wenn Elemente nach Priorität verarbeitet werden sollen - das Element mit höchster Priorität wird immer zuerst entnommen.
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.
Was ist der Unterschied zwischen TreeSet und PriorityQueue für priorisierte Elemente?
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:
SortedSet<Auftrag> s = new TreeSet<>(); // oder
Was bedeutet “amortisiert O(1)” bei ArrayList.add()?
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.
Wann verwendet man LinkedHashSet statt HashSet oder TreeSet?
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.
Warum ist Queue.poll() bei LinkedList O(1)?
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.
Warum wird im Anwendungsfall HashMap für die Artikelverwaltung gewählt?
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.
Warum werden im Anwendungsfall zwei Collections für Positionen verwendet (List + Map)?
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.
Wie hoch ist die Gesamtkomplexität im Auftrag-Verarbeitungsbeispiel?
Nachholen Seite 8 Aud Collection Framework
Wann ist TreeMap < LinkedHashMap < TreeSet > > sinnvoll trotz O(log N)?
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.
Wann ist TreeMap < LinkedHashMap < LinkedHashSet > > besser?
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.
Was ist das Konzept “bessere Laufzeit bei häufigen Operationen zum Preis schlechterer Laufzeit bei seltenen”?
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.
Last changed3 days ago