Mittel
Datenstrukturen
Array, Liste, Stack, Queue, Baum, Hashmap – Eigenschaften und Einsatz.
Warum Priorität „Mittel"? Gelegentlich Teil der Prüfung (40–59%). Verstehen, aber nicht überinvestieren.
Lernziele
- Array, Liste, Stack, Queue, Baum und HashMap unterscheiden
- Laufzeiten der Grundoperationen grob benennen
- Die passende Struktur für ein Szenario wählen
Überblick
| Struktur | Zugriff | Suchen | Einfügen | Einsatz |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | fester Index, schnelle Leseoperationen |
| Verkettete Liste | O(n) | O(n) | O(1) am Kopf | häufiges Einfügen/Löschen |
| Stack (LIFO) | — | — | O(1) | Undo, Call-Stack, Parser |
| Queue (FIFO) | — | — | O(1) | Druckerqueue, BFS |
| Binärbaum (balanciert) | — | O(log n) | O(log n) | sortierte Daten, schnelles Suchen |
| HashMap | — | O(1) Ø | O(1) Ø | schneller Key-Lookup |
Stolperfallen
- HashMap: O(1) nur amortisiert. Bei schlechter Hashfunktion Worst-Case O(n).
- Array vs. Liste: Array liest schnell, Liste fügt schnell ein.
- Unbalancierter Baum degeneriert zur Liste → Suche O(n).
Übungen
Eine AntwortWelche Struktur arbeitet nach FIFO?
Eine AntwortDurchschnittliche Zugriffszeit einer HashMap (nach Key)?
Zum Weiterlernen
▶
YouTubeÜberblick: Array, Liste, Stack, Queue
Kompakter Rundblick über die wichtigsten Datenstrukturen.
▶
YouTubeDatenstruktur Stack – Grundlagen und Pseudocode
Stack im Detail – LIFO-Prinzip mit Array- und Listen-Implementierung.
▶
YouTubeDatenstruktur Queue – Grundlagen und Pseudocode
Queue im Detail – FIFO-Prinzip mit Pseudocode.
Externe Inhalte – AP2 Lernhub ist nicht für die Verfügbarkeit oder Korrektheit der verlinkten Seiten verantwortlich.