Datenstrukturen verstehen: Array, Liste, Baum & Co.
Datenstrukturen bestimmen, wie Programme Daten speichern und verwalten. Die Wahl der richtigen Datenstruktur entscheidet über Laufzeit und Speicherverbrauch eines Algorithmus. Diese Karteikarten decken die wichtigsten klassischen Strukturen ab, die im Studium und in technischen Interviews gefragt werden.
Direkt loslernen
Lade alle 18 Karten mit einem Klick ins Tool. Hast du schon eigene Karten, kannst du die neuen anhängen. Dann lernst du sie mit Wiederholungsplan oder druckst sie als PDF.
Datenstrukturen nach Zugriffstyp einordnen
Unterscheide zuerst zwischen sequenziellen Strukturen (Array, Liste), stapelartigen Strukturen (Stack, Queue) und hierarchischen Strukturen (Baum, Heap). Graphen sind der allgemeinste Fall.
Komplexitäten verstehen, nicht auswendig lernen
- Array: Indexzugriff O(1), Suche O(n), Einfügen in der Mitte O(n) wegen Verschieben.
- Verkettete Liste: Einfügen am Anfang O(1), Suche O(n), kein wahlfreier Zugriff.
- Hash-Tabelle: Zugriff, Suche, Einfügen im Durchschnitt O(1), im Worst Case O(n) bei Kollisionen.
- Binärer Suchbaum (balanciert): Alle Operationen O(log n).
Anwendungsfälle kennen
Stack: Funktionsaufruf-Stack, Undo-Mechanismen, Klammerprüfung. Queue: Aufgabenwarteschlangen, BFS. Heap: Priority Queue, Heap-Sort. Trie: Autocomplete, Präfixsuche. B-Tree: Datenbank-Indizes.
Alle Karten in diesem Set
| Vorderseite | Rückseite |
|---|---|
| Array: Zeitkomplexität Indexzugriff | O(1), direkter Zugriff über Index |
| Array: Zeitkomplexität Suchen (unsortiert) | O(n), im Worst Case alle Elemente durchlaufen |
| Einfach verkettete Liste: Einfügen am Anfang | O(1), nur Zeiger umhängen, kein Verschieben nötig |
| Einfach verkettete Liste: Nachteil gegenüber Array | Kein wahlfreier Zugriff (kein O(1) per Index), mehr Speicher durch Zeiger |
| Stack: LIFO-Prinzip | Last In, First Out, das zuletzt eingefügte Element wird zuerst entnommen (push/pop) |
| Queue: FIFO-Prinzip | First In, First Out, das zuerst eingefügte Element wird zuerst entnommen (enqueue/dequeue) |
| Was ist ein binärer Suchbaum (BST)? | Jeder Knoten hat höchstens 2 Kinder. Linker Teilbaum: alle Werte kleiner. Rechter Teilbaum: alle Werte größer. |
| BST: Suche, Einfügen, Löschen (balancierter Baum) | O(log n), bei selbstbalancierenden Bäumen (AVL, Rot-Schwarz) auch im Worst Case. Bei unbalanciertem Baum O(n) im Worst Case. |
| Was ist ein Heap? | Vollständiger Binärbaum mit Heap-Eigenschaft: Max-Heap: jeder Elternknoten >= Kinder. Min-Heap: jeder Elternknoten <= Kinder. |
| Heap: Zugriff auf Maximum/Minimum | O(1): Beim Max-Heap liegt das Maximum, beim Min-Heap das Minimum in der Wurzel. |
| Hash-Tabelle: durchschnittliche Komplexität | Einfügen, Suchen, Löschen: O(1) im Durchschnitt, O(n) im Worst Case |
| Was ist eine Kollision in einer Hash-Tabelle? | Wenn zwei verschiedene Schlüssel auf denselben Hash-Wert (Bucket) abgebildet werden. |
| Kollisionsauflösung: Chaining vs. Open Addressing | Chaining: verlinkte Liste pro Bucket. Open Addressing: nächsten freien Platz suchen (z.B. lineare Sondierung). |
| Tiefe eines Baums vs. Höhe | Tiefe eines Knotens: Abstand zur Wurzel. Höhe des Baums: maximale Tiefe aller Knoten. |
| Was ist ein Graph? | Menge von Knoten (Vertices) und Kanten (Edges). Kann gerichtet oder ungerichtet, gewichtet oder ungewichtet sein. |
| Adjazenzmatrix vs. Adjazenzliste | Matrix: O(V²) Speicher, O(1) Kantenzugriff. Liste: O(V+E) Speicher, besser bei dünn besetzten Graphen. |
| Was ist ein Trie? | Baumstruktur für Zeichenketten. Jeder Pfad von der Wurzel zu einem als Wortende markierten Knoten repräsentiert ein Wort. Effizient für Präfixsuche. |
| Amortisierte Komplexität | Durchschnittliche Kosten einer Operation über eine Folge von n Operationen, z. B. dynamisches Array: Einfügen am Ende kostet O(1) amortisiert. |
Häufige Fragen
Wann nehme ich eine verlinkte Liste statt eines Arrays?
Wenn häufig Elemente am Anfang oder an einer bereits bekannten Position in der Mitte eingefügt oder gelöscht werden und kein wahlfreier Zugriff benötigt wird. Arrays sind besser bei häufigem Indexzugriff und cache-freundlichem Speicherlayout. In der Praxis sind Arrays oft die bessere Wahl, weil Cache-Lokalität stark ins Gewicht fällt.
Was bedeutet O(log n) in der Praxis?
Bei jedem Schritt halbiert sich das verbleibende Problem. Bei n = 1 Million Elementen braucht O(log n) etwa 20 Schritte statt 1 Million. Das ist der Grund, warum balancierte Bäume und binäre Suche so effizient sind.
Wann ist eine Hash-Tabelle langsam?
Wenn viele Kollisionen auftreten, z.B. durch eine schlechte Hash-Funktion oder einen hohen Füllgrad. Im Worst Case degeneriert sie zu O(n). Gute Implementierungen halten den Load Factor unter einer Grenze (z. B. 0,75) und vergrößern die Tabelle bei Überschreitung (Rehashing).