您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

數據結構基礎：循環單鏈表完整實現與迭代器適配

編輯：關於C++

循環單鏈表核心特徵

循環單鏈表與普通單鏈表的關鍵區別在於：尾節點的 next 指針指向頭哨兵節點，形成閉環結構。這帶來以下變化：

判空條件：first->next == first（而非 nullptr）
遍歷終止條件：node != first（而非 node != nullptr）
插入/刪除邏輯需相應調整指針指向

完整實現代碼

#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED

#include <iostream>
#include <stdexcept>
using namespace std;

// 前向聲明
template <typename Type> class MyList;
template <typename Type> class ListIterator;

// 節點定義
template <typename Type>
class Node {
    friend class MyList<Type>;
    friend class ListIterator<Type>;
    template <typename T>
    friend ostream &operator<<(ostream &os, const MyList<T> &list);

private:
    Node(const Type &dataValue) : data(dataValue), next(nullptr) {}
    Type data;
    Node *next;
};

// 循環鏈表類
template <typename Type>
class MyList {
    template <typename T>
    friend ostream &operator<<(ostream &os, const MyList<T> &list);
    friend class ListIterator<Type>;

public:
    MyList();
    ~MyList();
    void insertFront(const Type &data);
    void insert(const Type &data, int index);
    void remove(const Type &data);
    bool isEmpty() const;

private:
    Node<Type> *first;  // 頭哨兵節點
};

// --- 成員函數實現 ---

template <typename Type>
MyList<Type>::MyList() {
    first = new Node<Type>(0);
    first->next = first;  // 關鍵：指向自己形成環
}

template <typename Type>
MyList<Type>::~MyList() {
    Node<Type> *tmp = first;
    first = first->next;
    while (first != tmp) {
        Node<Type> *del = first;
        first = first->next;
        delete del;
    }
    delete tmp;  // 釋放頭哨兵
}

template <typename Type>
void MyList<Type>::insertFront(const Type &data) {
    Node<Type> *newNode = new Node<Type>(data);
    newNode->next = first->next;
    first->next = newNode;
}

template <typename Type>
void MyList<Type>::insert(const Type &data, int index) {
    int count = 1;
    Node<Type> *searchNode = first;
    // 終止條件改為 first
    while (count < index && searchNode->next != first) {
        ++count;
        searchNode = searchNode->next;
    }
    Node<Type> *newNode = new Node<Type>(data);
    newNode->next = searchNode->next;
    searchNode->next = newNode;
}

template <typename Type>
void MyList<Type>::remove(const Type &data) {
    if (isEmpty()) return;
    Node<Type> *previous = first;
    for (Node<Type> *searchNode = first->next; 
         searchNode != first;  // 終止條件
         searchNode = searchNode->next) {
        if (searchNode->data == data) {
            previous->next = searchNode->next;
            delete searchNode;
            if (previous->next == first) break;  // 到達尾部
            searchNode = previous->next;
        }
        previous = searchNode;
    }
}

template <typename Type>
bool MyList<Type>::isEmpty() const {
    return first->next == first;
}

// 輸出運算符
template <typename Type>
ostream &operator<<(ostream &os, const MyList<Type> &list) {
    for (Node<Type> *p = list.first->next; p != list.first; p = p->next) {
        os << p->data;
        if (p->next != list.first) cout << " -> ";
    }
    return os;
}

// ListIterator 適配：僅修改 isEmpty() 判斷邏輯
template <typename Type>
class ListIterator {
public:
    ListIterator(const MyList<Type> &_list) 
        : list(_list), currentNode((_list.first)->next) {}
    
    const Type &operator*() const throw(std::out_of_range);
    Type &operator*() throw(std::out_of_range);
    const Node<Type> *operator->() const throw(std::out_of_range);
    Node<Type> *operator->() throw(std::out_of_range);
    ListIterator &operator++() throw(std::out_of_range);
    ListIterator operator++(int) throw(std::out_of_range);
    bool isEmpty() const;

private:
    const MyList<Type> &list;
    Node<Type> *currentNode;
};

template <typename Type>
bool ListIterator<Type>::isEmpty() const {
    return currentNode == list.first;  // 判斷是否回到頭哨兵
}

// 其他運算符實現與單鏈表版本一致，此處省略
// ...

#endif

測試代碼與輸出

int main() {
    MyList<int> myList;
    for (int i = 0; i < 10; ++i) myList.insert(i+1, i+1);  // 1~10
    for (int i = 0; i < 5; ++i) myList.insertFront(i*10);   // 40 30 20 10 0 ...
    myList.insertFront(100);  // 100 40 30 20 10 0 1 2 3 4 5 6 7 8 9 10
    myList.remove(10);
    myList.remove(8);

    cout << "------------ MyList ------------" << endl;
    for (ListIterator<int> iter(myList); !iter.isEmpty(); ++iter)
        cout << *iter << ' ';
    cout << endl;

    cout << "Test: " << myList << endl;
    return 0;
}