Q1.4 – Höhere Datenstrukturen

Das Kerncurriculum verlangt hier keine Sammlung auswendig gelernter Strukturen. Im Mittelpunkt steht, Strukturen objektorientiert zu modellieren, ihre Operationen zu erklären und die Strukturwahl fachlich zu begründen.

E3 hat gezeigt: Ein Array speichert mehrere Werte geordnet und erlaubt direkten Zugriff über einen Index. Diese Struktur ist stark, solange Größe und Positionen gut planbar sind. Sie wird aber unhandlich, wenn Daten dynamisch wachsen, häufig in der Mitte eingefügt oder gelöscht werden oder nicht linear, sondern hierarchisch organisiert sind.

Q1.1 liefert die zweite Grundlage: Objekte können Attribute, Methoden und Referenzen besitzen. Aus einem Objekt wird ein Knoten, wenn es neben seinem Inhalt auch Verweise auf andere Knoten trägt. Aus einzelnen Knoten entsteht eine Datenstruktur, wenn Referenzen, Operationen und Regeln zusammenpassen.

Aus Q1.1 ist bekannt: Objekte werden nicht wie primitive Werte einfach kopiert. Variablen enthalten bei Objekten in der Regel Referenzen. Genau diese Idee wird in Q1.4 zur Strukturidee: Datenstrukturen entstehen, indem Objekte über Referenzen miteinander verbunden werden.

Für verkettete Listen bedeutet das: Die Liste besteht nicht aus nebeneinanderliegenden Speicherzellen wie ein Array. Stattdessen verweisen Knotenobjekte auf Nachfolger. Wer Referenzen versteht, kann nachvollziehen, warum Einfügen und Löschen bei verketteten Listen als Umlenken von Verweisen modelliert wird.

Eine Datenstruktur besteht damit aus drei zusammengehörigen Ebenen: Organisationsform, Operationen und Invarianten. Ein abstrakter Datentyp trennt zusätzlich die Frage Was darf man tun? von der Frage Wie ist es implementiert?

Stell dir eine Lerngruppe vor, die Quellenkarten für ein Referat sammelt. Neue Bücher und Webseiten kommen dazu, einzelne Karten werden umsortiert, fehlerhafte Angaben werden aktualisiert, manche Karten werden entfernt und am Ende sollen die Quellen in einer begründeten Reihenfolge abgearbeitet werden. Eine andere Situation wäre ein Bücherstapel: Das zuletzt aufgelegte Buch liegt oben. Eine Warteschlange arbeitet dagegen die zuerst Angekommenen zuerst ab.

Aus solchen Alltagssituationen entsteht die fachliche Frage nicht „Welche Struktur kenne ich?“, sondern: Welche Operationen treten häufig auf, und welche Regeln dürfen dabei nicht verletzt werden?

Ein abstrakter Datentyp ist ein Vertrag: Er beschreibt, welche Operationen erlaubt sind und welches Verhalten sie haben. Die konkrete Speicherung bleibt zunächst offen. Eine lineare Liste erlaubt zum Beispiel Zugriff, Aktualisierung, Einfügen, Löschen und Durchlaufen einer geordneten Folge.

interface Liste<T> {
  int length();
  boolean isEmpty();
  T get(int index);
  void set(int index, T value);
  void insert(int index, T value);
  T remove(int index);
}

Der Bezug zu Q1.1 ist direkt: Ein ADT ist eine fachliche Schnittstelle. Konkrete Klassen implementieren diese Schnittstelle und kapseln ihre interne Darstellung nach dem Geheimnisprinzip.

Die folgende Rendererfläche zeigt eine lineare Folge als ADT-Idee: sichtbar ist die Reihenfolge, nicht die interne Speicherung.

Die Deutung ist absichtlich abstrakt: Die Operationen sprechen über eine geordnete Folge. Ob die Folge später in einem Datenfeld oder in Knoten liegt, ist noch nicht entschieden.

Die array-basierte Liste greift die E3-Erfahrung mit Datenfeldern wieder auf. Ein Array speichert Werte an nummerierten Positionen. Deshalb ist get(i) stark: Die Position ist über den Index unmittelbar bestimmbar.

Der einfache Fall ist Aktualisieren: set(i, wert) verändert den Inhalt einer vorhandenen Zelle. Die Struktur bleibt gleich. Einfügen und Löschen sind dagegen Strukturänderungen: Nachfolgende Elemente müssen häufig verschoben werden, damit die Reihenfolge und die lückenlose Indexstruktur erhalten bleiben.

class ArrayListe {
  private int[] daten;
  private int anzahl;

  int get(int index) {
    return daten[index];
  }

  void set(int index, int wert) {
    daten[index] = wert;       // Inhalt ändert sich, Struktur bleibt gleich
  }
}

Beispiel: Einfügen an Position 1

Vor dem Renderer steht die Vorfrage: Welche Elemente müssen ihren Platz verlassen, damit an Position 1 ein neuer Wert eingefügt werden kann?

Die verkettete Liste ist der zentrale Q1.1-Anschluss in Q1.4. Ein Knoten ist ein Objekt mit Inhalt und Referenz: value speichert den Inhalt, next verweist auf den nächsten Knoten. Die Liste besitzt mit head einen Einstiegspunkt; je nach Implementierung kommen tail und current als Arbeitsreferenzen hinzu.

Bevor einzelne Operationen betrachtet werden, muss das Grundmodell der verketteten Liste klar sein: Ein Knoten speichert nicht nur einen Wert, sondern auch eine Referenz auf den nächsten Knoten. Die Liste besitzt mit head einen Einstiegspunkt. Von dort aus wird die Struktur Schritt für Schritt über next-Referenzen erschlossen.

Diese Darstellung macht zugleich die Grenze gegenüber dem Array sichtbar. Beim Array ist die Position über den Index unmittelbar erreichbar. In der verketteten Liste entsteht Position erst durch den Weg: Man beginnt bei head und folgt den next-Verweisen, bis der gesuchte Knoten erreicht ist.

class Node {
  int value;
  Node next;

  Node(int value) {
    this.value = value;
  }
}

Strukturmodell und Renderer

Die Abbildung sichert die Grundidee. Der Renderer zeigt anschließend dieselbe Struktur im Seitenkontext und macht sichtbar, welche Knoten beim Traversieren fokussiert werden.

Traversieren statt Direktzugriff

Traversieren bedeutet: current wandert entlang der next-Referenzen. Jede Bewegung folgt genau einer Verbindung. Deshalb ist der Zugriff auf eine spätere Position pfadbasiert und nicht direkt.

Node current = head;
while (current != null) {
  verarbeite(current.value);
  current = current.next;
}

Die fachliche Folgerung: Positionen sind in der verketteten Liste keine festen Adressen, sondern Ergebnisse einer Such- oder Laufbewegung.

Lokales Einfügen hinter current

Beim Einfügen ist nicht nur entscheidend, dass ein neuer Knoten entsteht. Entscheidend ist die Reihenfolge der Referenzänderungen. Wird zuerst current.next auf den neuen Knoten gesetzt, ohne den bisherigen Nachfolger zu sichern, kann der Rest der Liste unerreichbar werden.

Die Abbildung zeigt deshalb die sichere Reihenfolge: Zuerst übernimmt der neue Knoten mit new.next den bisherigen Nachfolger. Erst danach wird current.next auf den neuen Knoten umgelenkt. So bleibt die Restliste während der gesamten Operation erreichbar.

void insertAfterCurrent(Node current, Node neu) {
  neu.next = current.next;
  current.next = neu;
}

Der Renderer zeigt die Operation zusätzlich als schrittweise Strukturveränderung innerhalb der Seitenlogik.

Lokales Löschen hinter current

Beim Löschen hinter current wird kein ganzer Speicherbereich verschoben. Stattdessen wird eine Referenz so umgelenkt, dass der Nachfolger von current übersprungen wird.

Der entfernte Knoten ist danach nicht mehr Teil der logischen Listenstruktur. Entscheidend ist: Die Liste bleibt von head aus erreichbar, weil current nun direkt auf den nächsten relevanten Knoten verweist.

void removeAfterCurrent(Node current) {
  if (current == null || current.next == null) return;
  current.next = current.next.next;
}

Der Renderer ergänzt diese Referenzlogik als dynamische Darstellung. Er ersetzt die Bilddeutung nicht, sondern zeigt, wie die Operation im Ablauf gelesen werden kann.

Ein Stack ist nicht einfach „eine Liste, die senkrecht gezeichnet wird“. Als ADT legt er fest, dass nur ein Zugriffspunkt frei ist: top. Neue Elemente werden mit push oben abgelegt, pop entfernt genau das oberste Element, top oder peek liest es nur.

Vor dem Renderer steht die Vorfrage: Welches Element darf als nächstes entfernt werden, wenn nur top zugänglich ist?

Stack-Anwendungen sind Browser-Zurück, Undo-Funktionen, Klammerprüfung und der Call-Stack aus Q1.3: Rücksprunginformationen werden zuletzt abgelegt und zuerst wieder benötigt.

class Stack {
  private Node top;

  void push(int value) {
    Node neu = new Node(value);
    neu.next = top;
    top = neu;
  }
}

Objektorientiert nutzt ein Stack intern Knoten oder eine Liste, gibt aber nur Stack-Operationen frei. Das ist das Geheimnisprinzip aus Q1.1: Die interne Struktur bleibt gekapselt.

Eine Queue besitzt zwei definierte Enden: vorne front oder head, hinten tail. Mit enqueue wird hinten eingefügt, mit dequeue vorne entnommen. Dadurch entsteht FIFO: first in, first out.

Vor dem Renderer steht die Vorfrage: Welches Element muss als nächstes entnommen werden, damit die Ankunftsreihenfolge erhalten bleibt?

Typische Anwendungen sind Warteschlangen, Druckerwarteschlangen, Ticketsysteme, Ereignisverarbeitung und als Ausblick Breitensuche (BFS). Auch hier gilt Kapselung: Die interne Liste wird nicht direkt manipuliert, sondern über enqueue, dequeue und front genutzt.

class Queue {
  private Node head;
  private Node tail;

  void enqueue(int value) {
    Node neu = new Node(value);
    if (tail != null) tail.next = neu;
    tail = neu;
    if (head == null) head = neu;
  }
}

Warum lineare Strukturen nicht reichen

Listen, Stacks und Queues organisieren Daten linear. Viele Probleme sind aber verzweigt: Ordner enthalten Unterordner, Entscheidungen führen in unterschiedliche Suchräume, eine Organisation hat Über- und Unterordnungen. Dafür braucht man Strukturen, in denen ein Knoten mehrere Nachfolger besitzen kann.

Vor dem Renderer steht die Vorfrage: Welche Beziehungen kann eine lineare Liste nur umständlich ausdrücken?

Grundbegriffe sauber lesen

Teilbäume als Brücke zu Q1.3

Jeder Teilbaum ist wieder ein Baum. Genau diese Selbstähnlichkeit greift Q1.3 auf: Basisfall, Teilproblem und Rekursionsschritt lassen sich bei Baumoperationen besonders natürlich formulieren. Q1.4 fragt zusätzlich, welche Datenstruktur diese Operation überhaupt trägt.

void inorder(Node node) {
  if (node == null) return;     // Basisfall
  inorder(node.left);           // linker Teilbaum
  verarbeite(node.value);       // aktueller Knoten
  inorder(node.right);          // rechter Teilbaum
}

Binärer Baum und Traversierungen

Ein binärer Baum hat pro Knoten höchstens zwei Kinder: linken und rechten Teilbaum. Dadurch werden Traversierungen eindeutig beschreibbar: Preorder besucht zuerst den Knoten, Inorder zwischen linkem und rechtem Teilbaum, Postorder nach den Teilbäumen.

Inorder liefert im binären Suchbaum eine sortierte Reihenfolge, weil die Ordnungsregel für jeden Knoten gilt: links kleiner, rechts größer.

Binärer Suchbaum: Invariante und Operationen

Ein binärer Suchbaum ist ein binärer Baum mit Ordnungsregel. Diese Regel ist eine Invariante: Sie muss nach Suchen, Einfügen, Löschen und Aktualisieren gültig bleiben. Eine Aktualisierung des Schlüssels ist deshalb nicht beliebig harmlos; sie kann die Ordnungsregel verletzen und muss geprüft oder als Entfernen plus Einfügen modelliert werden.

Die folgenden Rendererflächen zeigen die Operationen nicht als Dekoration, sondern als Lesespuren im Suchbaum.

Strukturwahl ist keine Geschmackssache. Sie hängt davon ab, welche Operationen häufig sind, welche Invarianten gelten und ob die Daten linear, zugriffsbeschränkt oder hierarchisch organisiert werden müssen.

Welche Struktur passt, wenn ...?

Die PNG-Abbildungen sichern zentrale Referenzideen: Objektvariablen verweisen auf Objekte, Listen entstehen durch next-Verweise, Einfügen sichert zuerst den alten Nachfolger und Löschen schließt die Liste durch Referenzumlenkung. Die Renderer bleiben ergänzend wichtig, weil sie Operationen und Varianten im Seitenkontext schrittweise darstellen.

Der Rückbezug auf Q1.3 bleibt besonders im Baumteil wichtig: Viele Baumoperationen werden rekursiv formuliert. Q1.4 erweitert diesen Blick um die Strukturfrage: Welche Organisation der Daten macht die Operation überhaupt passend?