Arrays, Verkettete Listen, Stacks (LIFO), Queues (FIFO), Binäre Suchbäume & Heap vs. Stack.
Die richtige Wahl der Datenstruktur entscheidet über Speicherbedarf und Performance: Statische Arrays, einfach/doppelt verkettete Listen, Stacks, Queues, Binäre Suchbäume und Hash-Tabellen.
| Datenstruktur | Zugriff per Index | Einfügen am Anfang | Einfügen am Ende | Prinzip / Besonderheit |
|---|---|---|---|---|
| Array | $O(1)$ | $O(n)$ (Verschieben) | $O(1)$ (wenn Platz) | Fester, zusammenhängender Speicherblock |
| Verkettete Liste | $O(n)$ (Traversieren) | $O(1)$ (Pointer umhängen) | $O(1)$ mit Tail-Pointer | Knoten über Referenzen verknüpft |
| Stack | - | $O(1)$ (Push) | - | LIFO (Last In, First Out) - Aufruf-Stack, Undo-Funktion |
| Queue | - | $O(1)$ (Enqueue) | $O(1)$ (Dequeue) | FIFO (First In, First Out) - Druckwarteschlange |
| Hash-Tabelle | $O(1)$ (per Key) | $O(1)$ | $O(1)$ | Key $\rightarrow$ Hashfunktion $\rightarrow$ Bucket. Kollisionen: Chaining oder Open Addressing |
- Stack (Stapelspeicher): Schneller, automatischer Speicher für lokale primitive Variablen und Methodenaufrufe (Stack Frames). Feste Größe, führt bei endloser Rekursion zum StackOverflowError.
- Heap (Haufenspeicher): Großer, dynamischer Speicherbereich für Objekte und Instanzen. Verwaltung erfolgt durch den Garbage Collector (z. B. in Java, C#, Python) oder manuelle Freigabe (C/C++ mit malloc/free).
Bearbeiten Sie die Aufgaben und vergleichen Sie Ihre Antwort mit dem offiziellen Erwartungshorizont:
Erklären Sie die Landau-Symbole (O-Notation) zur Abschätzung der Zeitkomplexität. Ordnen Sie folgende Komplexitätsklassen von der effizientesten zur ineffizientesten Laufzeit: O(n log n), O(1), O(n²), O(log n), O(n). Nennen Sie je ein typisches Code- oder Algorithmenbeispiel für O(1), O(log n) und O(n).