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 alle klassischen Strukturen ab, die im Studium und in technischen Interviews gefordert werden.
Direkt loslernen
Lade alle 18 Karten mit einem Klick in den Lern-Modus, mische sie, lerne online oder drucke 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 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 max. 2 Kinder. Linkes Teilbaum: alle Werte kleiner. Rechtes Teilbaum: alle Werte größer. |
| BST – Suche, Einfügen, Löschen (balancierter Baum) | O(log n) im Durchschnitt – 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) – liegt immer 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^2) 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 zum Blatt 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: O(1) amortisiert für Einfügen. |
Häufige Fragen
Wann nehme ich eine verlinkte Liste statt eines Arrays?
Wenn häufig Elemente am Anfang oder in der Mitte eingefügt/gelöscht werden und kein wahlfreier Zugriff benötigt wird. Arrays sind besser bei häufigem Indexzugriff und cache-freundlichem Speicherlayout. In der Praxis dominieren Arrays fast überall, da Cache-Lokalität wichtig ist.
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 0.75 und rehassen dann die Tabelle.