Schulfach Informatik Studium

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.

18 Karteikarten · kostenlos · ohne Anmeldung

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).

Passende Lernsets