Verkettete Listen

Eine verkettete Liste (Linked List) ist eine dynamische Datenstruktur, bei der die Elemente (Knoten) nicht hintereinander im Speicher liegen, sondern über Zeiger (Referenzen) miteinander verbunden sind. Jeder Knoten enthält:

• Einen Datenteil (das gespeicherte Element)
• Einen Zeiger auf den nächsten Knoten

Der erste Knoten wird als Head (Kopf) bezeichnet. Der letzte Knoten zeigt auf null (Ende der Liste).

Bei einer einfach verketteten Liste hat jeder Knoten genau einen Zeiger – auf seinen Nachfolger. Die Liste kann nur in einer Richtung (vorwärts) durchlaufen werden.

// Java-Implementierung
class Knoten<T> {
    T daten;
    Knoten<T> nächster;

    Knoten(T daten) {
        this.daten = daten;
        this.nächster = null;
    }
}

class EinfachVerketteteListe<T> {
    private Knoten<T> head;

    // Am Anfang einfuegen: O(1)
    public void einfuegenVorne(T daten) {
        Knoten<T> neu = new Knoten<>(daten);
        neu.nächster = head;
        head = neu;
    }

    // Am Ende einfuegen: O(n)
    public void einfuegenHinten(T daten) {
        Knoten<T> neu = new Knoten<>(daten);
        if (head == null) { head = neu; return; }
        Knoten<T> aktüll = head;
        while (aktüll.nächster != null)
            aktüll = aktüll.nächster;
        aktüll.nächster = neu;
    }

    // Erstes Element löschen: O(1)
    public T löschenVorne() {
        if (head == null) return null;
        T daten = head.daten;
        head = head.nächster;
        return daten;
    }
}

Bei einer doppelt verketteten Liste hat jeder Knoten zwei Zeiger: einen auf den Nachfolger und einen auf den Vorgänger. Dies ermöglicht das Durchlaufen in beide Richtungen.

class DoppelKnoten<T> {
    T daten;
    DoppelKnoten<T> nächster;
    DoppelKnoten<T> vorheriger;

    DoppelKnoten(T daten) {
        this.daten = daten;
    }
}

Vorteile gegenüber der einfach verketteten Liste:

• Bidirektionales Traversieren (vorwärts und rückwärts)
• Effizientes Löschen eines bekannten Knotens in O(1), da der Vorgänger direkt erreichbar ist

Nachteil: Jeder Knoten benötigt mehr Speicher (zwei Zeiger statt einem).

• Einfügen am Anfang: O(1) – neuer Knoten wird Head
• Einfügen am Ende: O(n) bei einfacher Liste (Traversierung nötig), O(1) mit Tail-Zeiger
• Einfügen an Position i: O(i) – Traversierung bis zur Stelle
• Löschen am Anfang: O(1)
• Löschen eines bestimmten Knotens: O(n) bei einfacher Liste (Vorgänger suchen), O(1) bei doppelter Liste (wenn Knoten bekannt)
• Suchen: O(n) – sequentielles Durchlaufen nötig

• Speicher: Arrays haben feste Größe (oder müssen kopiert werden). Listen wachsen dynamisch.
• Zugriff auf Element i: Array: O(1) (Direktzugriff per Index). Liste: O(i) (Traversierung).
• Einfügen/Löschen am Anfang: Array: O(n) (alle Elemente verschieben). Liste: O(1).
• Einfügen/Löschen in der Mitte: Array: O(n). Liste: O(1) wenn Position bekannt, sonst O(n) zum Finden.
• Cache-Freundlichkeit: Arrays sind cache-freundlicher, da Elemente zusammenhängend im Speicher liegen. Listen verteilen Knoten über den gesamten Speicher.

• Zirkuläre (kreisförmige) Liste: Der letzte Knoten zeigt auf den ersten Knoten statt auf null. Ermöglicht endloses Durchlaufen.
• Liste mit Sentinel (Waechterknoten): Ein spezieller Dummy-Knoten am Anfang oder Ende vereinfacht die Implementierung, da Sonderfälle (leere Liste) entfallen.

Abitur-Tipp: Im Abitur wird häufig verlangt, das Einfügen oder Löschen in einer verketteten Liste grafisch darzustellen (Knoten mit Pfeilen). Übe das Umsetzen der Zeiger Schritt für Schritt. Typische Falle: Beim Löschen eines Knotens muss zuerst der Vorgänger aktualisiert werden. Vergiss nicht den Vergleich Array vs. verkettete Liste hinsichtlich Zugriffszeit, Einfüge-/Löschzeit und Speicherverbrauch.