Doppelt verkettete Liste in C++: Implementierung einer Queue und eines Stack mit Iteratoren

Einführung in doppelt verkettete Listen

Stell dir vor, du organisierst eine Warteschlange für das neueste KI-Update deiner Lieblings-App – jeder Nutzer hat eine eindeutige ID und eine Position. Genau so funktioniert eine doppelt verkettete Liste: Jedes Element (Node) kennt seinen Vorgänger und Nachfolger. Das ermöglicht effizientes Einfügen und Löschen an beiden Enden – perfekt für Queue (FIFO) und Stack (LIFO). In diesem Tutorial implementierst du eine templatisierte, doppelt verkettete Liste in C++, wie sie in der COP3504C Lab 09 gefordert wird. Du wirst sehen, wie du die Liste als Queue oder Stack nutzen kannst und einen Iterator schreibst, der dir erlaubt, die Elemente zu durchlaufen.

Grundlagen: Node und LinkedList

Jeder Knoten in der Liste speichert Daten (z.B. Koordinatenpaare) und zwei Zeiger: prev und next. Der front-Zeiger zeigt auf den ersten, back auf den letzten Knoten. Leere Listen zeigen auf nullptr. Hier ein minimales Gerüst:

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

template <typename T>
class LinkedList {
private:
    Node<T>* head;
    Node<T>* tail;
public:
    LinkedList() : head(nullptr), tail(nullptr) {}
    // ... Methoden
};

Queue-Operationen: enqueue und dequeue

Eine Queue funktioniert wie eine Ticket-Warteschlange beim Gaming-Event: Neue Spieler reihen sich hinten ein (enqueue), der vorderste wird als nächster bedient (dequeue). In der doppelt verketteten Liste fügst du am Ende (tail) ein und entfernst vom Anfang (head). Achte darauf, die Zeiger korrekt zu aktualisieren und Sonderfälle (leere Liste, ein Element) zu behandeln.

void enqueue(const 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;
}

Stack-Operationen: pop

Ein Stack verhält sich wie der Verlauf in deinem Browser – der letzte Eintrag wird zuerst angezeigt (LIFO). Für einen Stack fügst du am Ende ein (wie bei enqueue) und entfernst mit pop das letzte Element. Hier entfernst du vom tail:

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

Iterator-Klasse: Durch die Liste navigieren

Ein Iterator erlaubt es, die Liste wie einen Container der STL zu durchlaufen. Du implementierst begin(), end() und die Operatoren *, ++, --, ==, !=. Der end()-Iterator zeigt auf einen speziellen Zustand (z.B. nullptr). Hier ein Ausschnitt:

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& other) const { return current == other.current; }
    bool operator!=(const Iterator& other) const { return current != other.current; }
};

Iterator begin() const { return Iterator(head); }
Iterator end() const { return Iterator(nullptr); }

Weitere Methoden: contains, remove, clear

Mit contains(T element) prüfst du, ob ein bestimmtes Element in der Liste existiert – nützlich, wenn du z.B. in einer Finanz-App prüfen willst, ob eine Transaktions-ID bereits verarbeitet wurde. remove(T element) löscht den ersten Knoten mit diesem Wert. Hier musst du vier Fälle unterscheiden: Löschen des ersten, eines mittleren, des letzten oder des einzigen Knotens. clear() löscht alle Knoten – eine Schleife, die jeden Knoten einzeln freigibt.

Häufige Fehler und Tipps

Vergiss nicht, nach jeder Modifikation die Zeiger konsistent zu halten. Nutze Memory-Leak-Detection (z.B. nvwa) und teste mit dem mitgelieferten main.cpp. Achte auf exakte Ausgabe – ZyLabs vergleicht Zeichen für Zeichen. Verwende const wo sinnvoll, z.B. bei getFront() und getBack(). Der Iterator muss nach end() zeigen, wenn er über das Ende hinausläuft.

Fazit

Mit dieser Implementierung hast du eine flexible doppelt verkettete Liste, die du sowohl als Queue als auch als Stack nutzen kannst. Das Verständnis von Zeigern und dynamischem Speicher ist essenziell für fortgeschrittene C++-Programmierung – und ein echter Gamechanger, wenn du später eigene Datenstrukturen für KI-Algorithmen oder Echtzeitsysteme entwickelst. Viel Erfolg bei deiner Abgabe!