Doppelt verkettete Liste in C++: Tutorial zur Implementierung von LinkedList und Iterator

Einführung in doppelt verkettete Listen

Eine doppelt verkettete Liste ist eine dynamische Datenstruktur, bei der jedes Element (Knoten) sowohl einen Zeiger auf den nächsten als auch auf den vorherigen Knoten enthält. Dadurch lassen sich Operationen wie Einfügen und Löschen an beiden Enden effizient durchführen. In diesem Tutorial lernst du, wie du eine solche Liste in C++ mit einer LinkedList-Klasse und einem verschachtelten Iterator implementierst – genau wie in der COP3504C Lab 09-Aufgabe.

Warum doppelt verkettete Liste?

Stell dir vor, du entwickelst eine Warteschlange für ein KI-Chatsystem, das Anfragen in Echtzeit verarbeitet. Oder du baust eine Undo-Funktion für eine Zeichen-App – doppelt verkettete Listen sind ideal, weil du in beide Richtungen navigieren kannst. Auch in der Spieleentwicklung, etwa für die Verwaltung von Spielerzügen in einer Rundenstrategie, kommen sie zum Einsatz. Die doppelt verkettete Liste verbindet Flexibilität mit Effizienz.

Grundlegende Struktur: Knoten und Liste

Jeder Knoten speichert die Daten (z. B. Koordinatenpaare) und zwei Zeiger: next (zeigt auf den folgenden Knoten) und prev (zeigt auf den vorherigen). Die Liste selbst verwaltet Zeiger auf den ersten (front) und letzten Knoten (back). Enden zeigen auf nullptr.

template <typename T>
struct Node {
    T data;
    Node* next;
    Node* prev;
    Node(const T& val) : data(val), next(nullptr), prev(nullptr) {}
};

LinkedList-Klasse: Konstruktor und Basismethoden

Der Konstruktor initialisiert eine leere Liste. Die Methode isEmpty() prüft, ob die Liste leer ist. getFront() und getBack() geben das erste bzw. letzte Element zurück – nützlich für Stack/Queue-Operationen.

template <typename T>
class LinkedList {
private:
    Node<T>* head;
    Node<T>* tail;
public:
    LinkedList() : head(nullptr), tail(nullptr) {}
    bool isEmpty() const { return head == nullptr; }
    T getFront() const { return head->data; }
    T getBack() const { return tail->data; }
    // ...
};

Iterator-Klasse: Navigieren durch die Liste

Ein Iterator erlaubt es, die Liste zu durchlaufen, ohne die interne Struktur offenzulegen. In der COP3504C Lab 09-Aufgabe wird ein verschachtelter Iterator verlangt, der die Operatoren *, ++, --, == und != implementiert.

class Iterator {
private:
    Node<T>* current;
public:
    Iterator(Node<T>* node) : current(node) {}
    T operator*() const { return current->data; }
    Iterator& operator++() {
        if (current) current = current->next;
        return *this;
    }
    Iterator& operator--() {
        if (current) current = current->prev;
        return *this;
    }
    bool operator==(const Iterator& rhs) const { return current == rhs.current; }
    bool operator!=(const Iterator& rhs) const { return current != rhs.current; }
};

Wichtig: begin() gibt einen Iterator auf den ersten Knoten zurück, end() einen Iterator, der auf nullptr zeigt („past-the-end“). tail() zeigt auf den letzten Knoten.

Queue- und Stack-Operationen: enqueue, dequeue, pop

Eine doppelt verkettete Liste kann sowohl als Queue (FIFO) als auch als Stack (LIFO) verwendet werden. Für die Queue fügst du mit enqueue am Ende ein und entfernst mit dequeue vom Anfang. Für den Stack entfernst du mit pop das letzte Element.

void enqueue(T element) {
    Node<T>* newNode = new Node<T>(element);
    if (isEmpty()) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
}

void dequeue() {
    if (isEmpty()) return;
    Node<T>* temp = head;
    head = head->next;
    if (head) head->prev = nullptr;
    else tail = nullptr;
    delete temp;
}

void pop() {
    if (isEmpty()) return;
    Node<T>* temp = tail;
    tail = tail->prev;
    if (tail) tail->next = nullptr;
    else head = nullptr;
    delete temp;
}

contains- und remove-Methoden

contains(T element) durchläuft die Liste und prüft, ob ein Element vorhanden ist. remove(T element) entfernt den ersten Knoten mit dem angegebenen Wert – dabei müssen vier Fälle beachtet werden: Entfernen des ersten, mittleren, letzten oder einzigen Knotens.

bool contains(T element) const {
    Node<T>* current = head;
    while (current) {
        if (current->data == element) return true;
        current = current->next;
    }
    return false;
}

void remove(T element) {
    Node<T>* current = head;
    while (current) {
        if (current->data == element) {
            if (current == head) {
                dequeue();
            } else if (current == tail) {
                pop();
            } else {
                current->prev->next = current->next;
                current->next->prev = current->prev;
                delete current;
            }
            return;
        }
        current = current->next;
    }
}

clear-Methode: Speicher freigeben

clear() löscht alle Knoten und setzt die Zeiger zurück – unverzichtbar, um Speicherlecks zu vermeiden. In der Lab-Aufgabe ist die Speicherverwaltung mit nvwa integriert.

void clear() {
    while (!isEmpty()) {
        dequeue();
    }
}

Praxisbeispiel: Koordinaten-Pfad wie in einer Navigations-App

Stell dir vor, du speicherst Wegpunkte einer Route in einer doppelt verketteten Liste. Jeder Knoten enthält (x,y)-Koordinaten. Mit dem Iterator kannst du vorwärts und rückwärts navigieren – ähnlich wie bei einer Undo-Funktion in einer Zeichen-App. Wenn ein Nutzer einen Zwischenstopp einfügt, verwendest du enqueue oder fügst an einer bestimmten Stelle ein. Das Entfernen eines abbiegenden Punktes erfolgt mit remove.

Häufige Fehler und Tipps

• Zeiger nicht aktualisiert: Achte darauf, dass bei remove die prev- und next-Zeiger der benachbarten Knoten korrekt gesetzt werden.
• Speicherleck: Vergiss nicht, gelöschte Knoten mit delete freizugeben.
• Iterator nach Löschen: Ein Iterator, der auf einen gelöschten Knoten zeigt, wird ungültig – verwende ihn nicht weiter.
• Randfälle testen: Leere Liste, nur ein Element, Element am Anfang/Ende entfernen.

Fazit

Die Implementierung einer doppelt verketteten Liste in C++ ist eine hervorragende Übung, um Zeiger, dynamische Speicherverwaltung und Iterator-Muster zu verstehen. Mit den Methoden enqueue, dequeue, pop, contains und remove deckst du die typischen Anforderungen der COP3504C Lab 09-Aufgabe ab. Nutze die Trendbeispiele aus der KI- oder Spieleentwicklung, um die Konzepte lebendig zu machen. Viel Erfolg beim Coden!