Kernpunkte

• Array (statisch): O(1)-Zugriff per Index, O(n)-Einfügen/Löschen wegen Verschiebung. Feste Größe in Java (`int[]`).
• Verkettete Liste: jedes Element zeigt auf seinen Nachfolger; O(1)-Einfügen/Löschen am Kopf, O(n)-Zugriff.
• Stack (LIFO): Operationen `push`, `pop`, `peek` — z.B. Methoden-Aufrufstack, Klammerprüfung, Rückgängig-Funktion.
• Queue (FIFO): Operationen `enqueue`, `dequeue` — z.B. Drucker-Warteschlange, BFS-Frontier.
• Deque (doppelt verkettet) kombiniert Stack- und Queue-Operationen mit O(1) an beiden Enden.
• Skelett verkettete Liste: ```java class Knoten<T> { T wert; Knoten<T> next; } class Liste<T> { Knoten<T> kopf; void einfügenKopf(T x) { Knoten<T> n = new Knoten<>(); n.wert = x; n.next = kopf; kopf = n; } } ```

Kernpunkte

• Ein Binärbaum hat je Knoten höchstens zwei Kinder; Tiefe d, Höhe h, vollständig wenn alle Ebenen bis auf evtl. die letzte gefüllt.
• Binärer Suchbaum (BST): links < Knoten < rechts; Operationen suchen/einfügen/löschen in O(h), bei Entartung O(n).
• Traversierungen: Preorder (Wurzel-Links-Rechts), Inorder (Links-Wurzel-Rechts — liefert sortierte Reihenfolge bei BST), Postorder (Links-Rechts-Wurzel), Levelorder (BFS).
• Balancierung: AVL- oder Rot-Schwarz-Bäume halten Höhe in O(log n); Java `TreeMap` nutzt Rot-Schwarz.
• Heap: vollständiger Binärbaum mit Heap-Bedingung; Grundlage für Priority Queue und Heapsort, O(log n) je Operation.
• Code-Skelett BST: ```java Knoten suchen(Knoten n, int key) { if (n == null || n.wert == key) return n; return key < n.wert ? suchen(n.links, key) : suchen(n.rechts, key); } ```

Kernpunkte

• Ein Graph G = (V, E) besteht aus Knotenmenge V und Kantenmenge E; gerichtet/ungerichtet, gewichtet/ungewichtet, zyklisch/azyklisch.
• Repräsentation: Adjazenzmatrix (|V|² Speicher, O(1)-Kantencheck) oder Adjazenzliste (sparsamer für dünne Graphen).
• Breitensuche (BFS): nutzt Queue, findet kürzeste Pfade in ungewichteten Graphen, Laufzeit O(|V| + |E|).
• Tiefensuche (DFS): nutzt Stack/Rekursion, erzeugt Spannbaum, klassifiziert Kanten in Baum-, Rück-, Vorwärts-, Querkante.
• Dijkstra-Algorithmus: kürzeste Pfade in gewichteten Graphen mit nicht-negativen Kanten; mit Priority Queue O((|V| + |E|) log |V|).
• Anwendungen: Routenplanung (Dijkstra/A*), soziale Netzwerke, Compiler (Abhängigkeitsgraph), Webcrawler.
• Querverweis: Dijkstra ist ein Greedy-Verfahren (Topic Algorithmen und Programmierung) und nutzt die Priority Queue aus dem Abschnitt Heaps dieses Topics.

Kernpunkte

• Eine Hashfunktion bildet Schlüssel auf einen Bucket-Index ab; gut, wenn sie gleichmäßig verteilt und schnell berechenbar ist.
• Kollisionsbehandlung: Separate Chaining (Bucket enthält verkettete Liste) vs. Open Addressing (linear/quadratic probing, double hashing).
• Lastfaktor α = n / m mit n Elementen und m Buckets; bei α > 0.75 typischerweise Rehashing auf doppelte Buckets.
• Durchschnittliche Laufzeit O(1) für put/get/remove; im Worst-Case (alle kollidieren) degeneriert zu O(n).
• Java `HashMap` nutzt seit Java 8 ab Schwelle 8 einen Rot-Schwarz-Baum statt verketteter Liste pro Bucket — verhindert DoS-Angriffe durch Hash-Kollisionen.
• Anwendungen: Datenbank-Indizes, Caches, Set-Datentyp, Deduplizierung.

Kernpunkte

• Ein abstrakter Datentyp (ADT) definiert eine Menge von Werten zusammen mit Operationen, ohne die Implementation festzulegen — Trennung von Was (Spezifikation) und Wie (Realisierung).
• Beispiel ADT Stack: `push(x)`, `pop()`, `peek()`, `isEmpty()` — die Schnittstelle ist unabhängig davon, ob ein Array oder eine verkettete Liste zugrunde liegt.
• In Java realisiert ein Interface den ADT-Vertrag; in Python erfüllt eine Klasse implizit ein Protokoll über die erwarteten Methoden („Duck Typing").
• Generische Typen (Java `<T>`, Python Type Hints) erlauben typsichere, wiederverwendbare Container ohne Casts: `Stack<String>` vs. `Stack<Integer>`.
• Vorteile der ADT-Sicht: austauschbare Implementation, lokal begrenzte Änderungen, klar prüfbare Invarianten, leichtere Wiederverwendung.
• Wahl der zugrunde liegenden Struktur richtet sich nach dem dominanten Zugriffsmuster (wahlfreier Zugriff → Array; häufiges Einfügen am Anfang → verkettete Liste).
• ADT-Skelett: ```java interface Stapel<T> { void push(T x); T pop(); boolean isEmpty(); } ```

Kernpunkte

• Ein Binär-Heap ist ein vollständiger Binärbaum mit Heap-Bedingung: im Min-Heap ist jeder Knoten ≤ seine Kinder, im Max-Heap ≥.
• Speicherung im Array: für Index i liegt das linke Kind bei 2i+1, das rechte bei 2i+2, der Vater bei ⌊(i−1)/2⌋ — kein Zeiger-Overhead.
• Priority Queue: liefert stets das Element höchster (bzw. niedrigster) Priorität; Standard-Implementation ist ein Heap mit O(log n) für Einfügen und Entfernen.
• Operationen: `insert` (Element ans Ende, dann sift-up), `extractMin/Max` (Wurzel entnehmen, letztes Element an die Spitze, dann sift-down).
• Heapsort: Array zum Max-Heap aufbauen (O(n) per Floyd-Heapify), dann wiederholt Wurzel ans Ende tauschen — Gesamtlaufzeit O(n log n), in-place, aber nicht stabil.
• Anwendungen: Dijkstra/A* (Knotenpriorität), Ereignissimulation, Task-Scheduler, Top-k-Auswahl, Median-Streaming (zwei Heaps).
• Java stellt `PriorityQueue<E>` bereit; standardmäßig ein Min-Heap über die natürliche Ordnung oder einen Comparator.