Datenstrukturen — Arrays, Listen und Bäume

Einführung

Ein Programm ist mehr als seine Algorithmen. Es braucht auch eine Struktur, um Daten zu speichern, zu verwalten und schnell darauf zuzugreifen. Die Wahl der richtigen Datenstruktur entscheidet oft darüber, ob ein Programm in Millisekunden oder Sekunden antwortet.

Wenn du Kontakte auf deinem Handy speicherst, wird eine andere Struktur verwendet als beim Browser-Verlauf oder beim Datei-System. Jede Datenstruktur hat Stärken und Schwächen — in bestimmten Operationen brilliert sie, in anderen versagt sie.

Diese Lektion zeigt dir die wichtigsten Datenstrukturen, wie sie aufgebaut sind, und wann du welche verwendest.

Grundidee

Datenstrukturen sind Wege, Daten zu organisieren. Die gleichen Daten können auf verschiedene Arten gespeichert werden — und das beeinflusst, wie schnell du Elemente einfügst, löschst oder findest.

Stell dir eine Bibliothek vor: Bücher in zufälliger Reihenfolge (Array, schlecht sortiert), Bücher alphabetisch (sortiertes Array), Bücher mit Zettelkatalog (HashMap), Bücher nach Themenbaum geordnet (Baum). Dieselben Bücher, völlig unterschiedliche Organisation.

Erklärung

Array

Ein Array ist eine geordnete Folge von Elementen, die direkt nebeneinander im Speicher liegen.

Eigenschaften:

• Zugriff per Index in O(1) — extrem schnell: arr[5] geht sofort, weil der Speicherort berechenbar ist.
• Einfügen am Ende: O(1) (meistens). Einfügen in der Mitte: O(n) — alle nachfolgenden Elemente müssen verschoben werden.
• Löschen in der Mitte: O(n) — dasselbe Problem.
• Feste oder dynamische Größe (je nach Sprache).

Wann Array? Wenn du oft per Index zugreifst und selten einfügst oder löschst. Gut für Matrizen, Pixel, Zeitreihen.

Verkettete Liste (Linked List)

Bei einer verketteten Liste ist jedes Element ein Knoten, der einen Wert und einen Zeiger (Verweis) auf den nächsten Knoten enthält.

[3 | •]→[7 | •]→[1 | •]→[null]

Eigenschaften:

• Zugriff per Index: O(n) — du musst von vorne durchlaufen.
• Einfügen/Löschen am Anfang: O(1) — nur Zeiger ändern.
• Einfügen/Löschen in der Mitte: O(n) für Suche, dann O(1) für Umhängen.
• Kein zusammenhängender Speicher nötig — flexibel.

Wann Liste? Wenn du viel einfügst und löschst, besonders am Anfang. Gut für Queues, Undo-Historien.

Stapel (Stack) — LIFO

Ein Stapel folgt dem Prinzip LIFO: Last In, First Out. Das zuletzt eingefügte Element wird als erstes entnommen — wie ein Stapel Teller.

Zwei Operationen:

• push(x) — lege x oben drauf.
• pop() — nimm das oberste Element ab.

Alltag: Der Browser-Verlauf ist ein Stapel. Jede besuchte Seite wird oben draufgelegt. Der Zurück-Knopf nimmt oben ab. Die Funktion „Rückgängig” in Textverarbeitungsprogrammen funktioniert genauso.

Der Call Stack beim Programmieren (den du aus der Lektion zu Rekursion kennst) ist ebenfalls ein Stapel: Jeder Funktionsaufruf wird oben draufgelegt, jede Rückkehr nimmt ihn ab.

Warteschlange (Queue) — FIFO

Eine Warteschlange folgt dem Prinzip FIFO: First In, First Out. Das zuerst eingefügte Element wird als erstes entnommen — wie eine Schlange an der Kasse.

Zwei Operationen:

• enqueue(x) — stelle x hinten an.
• dequeue() — nimm das vorderste Element.

Alltag: Druckerwarteschlange — der erste Druckauftrag wird zuerst gedruckt. Netzwerkpakete werden in Reihenfolge verarbeitet. Aufgaben in einem Server warten in einer Queue.

Baum

Ein Baum ist eine hierarchische Datenstruktur mit Knoten, die durch Kanten verbunden sind. Es gibt genau einen Wurzelknoten (root), von dem alle anderen abstammen. Knoten ohne Kinder heißen Blätter.

         [8]
        /   \
      [3]   [10]
      / \      \
    [1] [6]   [14]

Eigenschaften:

• Keine Zyklen (kein Weg führt zurück zu einem Vorgänger).
• Jeder Knoten hat genau einen Elternknoten (außer der Wurzel).

Binärer Suchbaum (BST)

Ein binärer Suchbaum hat eine zusätzliche Eigenschaft: Für jeden Knoten gilt — alle Werte im linken Teilbaum sind kleiner, alle im rechten größer.

Im Beispiel oben: Links von 8 liegt 3 (kleiner), rechts 10 (größer). Links von 3 liegt 1 (kleiner), rechts 6 (größer).

Suchen: Du vergleichst den gesuchten Wert mit dem aktuellen Knoten. Kleiner → geh links. Größer → geh rechts. Gleich → gefunden. Jeder Schritt halbiert den Suchraum. Bei einem balancierten Baum: O(log n).

Alltag: Datei-System deines Computers ist ein Baum (Ordner enthält Unterordner und Dateien). HTML-Dokumente sind Bäume (DOM). Entscheidungsbäume in KI.

HashMap (Hashtabelle)

Eine HashMap erlaubt es, Daten per Schlüssel zu speichern und in O(1) (im Durchschnitt) darauf zuzugreifen.

Idee: Eine Hashfunktion berechnet aus dem Schlüssel (z. B. einem Wort) eine Indexzahl. Unter diesem Index wird der Wert gespeichert.

hashfunktion("name") → Index 4
hashfunktion("alter") → Index 7

Kollision: Zwei Schlüssel können denselben Index ergeben (Kollision). Dafür gibt es Lösungsstrategien (z. B. jeder Platz enthält eine verkettete Liste).

Eigenschaften:

• Einfügen, Löschen, Suchen: O(1) im Durchschnitt.
• Reihenfolge der Elemente nicht definiert.

Alltag: Jedes Wörterbuch oder Dictionary in Python, JavaScript etc. ist eine HashMap. Datenbankindizes. Caches (Webseite gecacht? Schau in der HashMap nach).

Abstrakte Datentypen

Stapel, Warteschlange und Map sind abstrakte Datentypen (ADTs): Sie definieren, welche Operationen möglich sind — nicht wie sie intern gespeichert werden. Ein Stapel kann durch ein Array oder eine verkettete Liste implementiert werden. Die Schnittstelle bleibt gleich.

Beispiel aus dem Alltag

Browser-Verlauf (Stapel): Jede besuchte Seite wird auf den Stapel gelegt. „Zurück” nimmt oben ab. „Vorwärts” ist ein zweiter Stapel — das Forward-Stack.

Druckerwarteschlange (Queue): Du druckst drei Dokumente hintereinander. Sie kommen in der Reihenfolge des Eintretens an den Drucker — FIFO.

Dateisystem (Baum): Dein Desktop ist ein Knoten. Darin ein Ordner „Schule” — ein Kindknoten. Darin „Physik” und „Mathe” — weitere Kinder. Dateien darin sind Blätter. Die Struktur ist ein Baum.

Wörterbuch-Lookup (HashMap): Du gibst in einer App ein Wort ein, die App überprüft sofort, ob es im Wörterbuch steht. Das geht in O(1) — weil die HashMap die Hashfunktion anwendet und direkt den richtigen Platz nachschlägt. Keine Schleife durch alle Wörter nötig.

Anwendung

Für jede der folgenden Situationen: Welche Datenstruktur passt am besten?

1. Du baust eine „Undo/Redo”-Funktion in einem Texteditor.
2. Ein Webserver soll Anfragen in der Reihenfolge ihres Eintreffens abarbeiten.
3. Du speicherst die Einwohnerzahl aller deutschen Städte und möchtest schnell nach Stadtname suchen.
4. Du modellierst ein Dateisystem mit Ordnern und Unterordnern.
5. Du speicherst eine Liste von Messwerten einer Wetterstation, auf die du per Index zugreifst.

Begründe jeweils kurz deine Wahl.

Typische Fehler

Array immer nehmen: Arrays sind nicht universell optimal. Wenn häufig in der Mitte eingefügt oder gelöscht wird, ist eine verkettete Liste besser.

HashMap als Allheilmittel: HashMaps sind schnell beim Nachschlagen per Schlüssel, aber ungeordnet. Wenn du Daten sortiert brauchst, ist ein Baum oder sortiertes Array besser.

Baum mit Liste verwechseln: Ein Baum ist eine hierarchische Struktur. Nicht jede Liste ist ein Baum. Entscheidend: Bäume haben genau einen Elternknoten pro Knoten (außer der Wurzel) und keine Zyklen.

O(n) beim BST vergessen: Ein Binärer Suchbaum ist nur O(log n) bei balanciertem Baum. Ein unbalancierter Baum (z. B. alle Elemente in aufsteigender Reihenfolge eingefügt) degeneriert zur verketteten Liste — dann O(n). Deshalb gibt es selbstbalancierende Bäume wie AVL oder Rot-Schwarz-Bäume.

Zusammenfassung

• Array: direkter Indexzugriff in O(1), aber Einfügen/Löschen in der Mitte teuer (O(n))
• Verkettete Liste: Einfügen/Löschen am Anfang in O(1), aber Indexzugriff langsam (O(n))
• Stapel (LIFO): gut für Undo, Call Stack, Tiefensuche
• Warteschlange (FIFO): gut für Aufgabenverarbeitung, Druckerwarteschlange, Breitensuche
• Binärer Suchbaum: Suchen, Einfügen, Löschen in O(log n) bei balanciertem Baum
• HashMap: Schlüssel-Wert-Zugriff in O(1) im Durchschnitt; keine definierte Reihenfolge

Quiz

Frage 1: Was ist der wichtigste Unterschied zwischen Array und verketteter Liste — und wann ist welche die bessere Wahl?

Frage 2: Was ist der Unterschied zwischen Stapel (Stack) und Warteschlange (Queue) — und nenne je ein Alltagsbeispiel?

Frage 3: Wie funktioniert ein Binärer Suchbaum — und warum ist Suchen darin schnell?

Frage 4: Wie funktioniert eine HashMap — und was ist eine Kollision?