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

數據結構基礎：雙向循環鏈表完整實現與雙向迭代器

編輯：關於C++

雙向循環鏈表優勢

查詢：與單鏈表相同
插入/刪除：需同時維護 prev 和 next 兩個方向指針
尾部操作 O(1)：憑藉 first->prev 直接定位尾節點，極適合頻繁尾部插入場景

雙向循環鏈表結構空鏈表結構

節點與鏈表定義

template <typename Type>
class DoubleListNode {
    friend class DoubleList<Type>;
    friend class ListIterator<Type>;
    template <typename T>
    friend ostream &operator<<(ostream &os, const DoubleList<T> &list);

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

template <typename Type>
class DoubleList {
    friend class ListIterator<Type>;
    template <typename T>
    friend ostream &operator<<(ostream &os, const DoubleList<T> &list);

public:
    DoubleList();
    ~DoubleList();
    void push_back(const Type &data);
    void push_front(const Type &data);
    void insert(int position, const Type &data);
    void pop_front();
    void pop_back();
    void remove(const Type &removeData);
    bool search(const Type &searchData) const;
    bool isEmpty() const { return first->next == first; }

private:
    void insertPrivate(DoubleListNode<Type> *previous, DoubleListNode<Type> *x);
    void removePrivate(DoubleListNode<Type> *x);
    DoubleListNode<Type> *first;
};

核心私有輔助函數

// 構造：頭哨兵 self-loop
template <typename Type>
DoubleList<Type>::DoubleList() {
    first = new DoubleListNode<Type>(0);
    first->next = first;
    first->prev = first;
}

// 析構：遍歷釋放
template <typename Type>
DoubleList<Type>::~DoubleList() {
    DoubleListNode<Type> *tmp = first;
    first = first->next;
    while (first != tmp) {
        DoubleListNode<Type> *del = first;
        first = first->next;
        delete del;
    }
    delete tmp;
}

// 插入核心：previous 後插入 x
template <typename Type>
void DoubleList<Type>::insertPrivate(DoubleListNode<Type> *previous, DoubleListNode<Type> *x) {
    x->prev = previous;
    x->next = previous->next;
    previous->next->prev = x;
    previous->next = x;
}

// 刪除核心：移除 x（不可刪頭哨兵）
template <typename Type>
void DoubleList<Type>::removePrivate(DoubleListNode<Type> *x) {
    if (x == first) throw std::range_error("permission denied to delete first pointer");
    x->prev->next = x->next;
    x->next->prev = x->prev;
    delete x;
}

公開接口實現

// 尾插 O(1)
template <typename Type>
void DoubleList<Type>::push_back(const Type &data) {
    DoubleListNode<Type> *newNode = new DoubleListNode<Type>(data);
    insertPrivate(first->prev, newNode);  // first->prev 即尾節點
}

// 頭插 O(1)
template <typename Type>
void DoubleList<Type>::push_front(const Type &data) {
    DoubleListNode<Type> *newNode = new DoubleListNode<Type>(data);
    insertPrivate(first, newNode);  // first 後即頭節點
}

// 任意位置插入（1-based）
template <typename Type>
void DoubleList<Type>::insert(int position, const Type &data) {
    if (position == 1) return push_front(data);
    int count = 1;
    DoubleListNode<Type> *previous = first->next;
    while (count < position-1 && previous != first) {
        ++count; previous = previous->next;
    }
    if (previous == first) return push_back(data);  // 越界尾插
    DoubleListNode<Type> *newNode = new DoubleListNode<Type>(data);
    insertPrivate(previous, newNode);
}

// 刪除頭/尾
template <typename Type> void DoubleList<Type>::pop_front() { removePrivate(first->next); }
template <typename Type> void DoubleList<Type>::pop_back() { removePrivate(first->prev); }

// 刪除所有值為 removeData 的節點
template <typename Type>
void DoubleList<Type>::remove(const Type &removeData) {
    if (isEmpty()) throw std::range_error("link list is empty");
    for (DoubleListNode<Type> *p = first->next; p != first; p = p->next) {
        if (p->data == removeData) removePrivate(p);
    }
}

// 查找
template <typename Type>
bool DoubleList<Type>::search(const Type &searchData) const {
    for (DoubleListNode<Type> *p = first->next; p != first; p = p->next)
        if (p->data == searchData) return true;
    return false;
}

// 輸出
template <typename Type>
ostream &operator<<(ostream &os, const DoubleList<Type> &list) {
    for (DoubleListNode<Type> *p = list.first->next; p != list.first; p = p->next)
        os << p->data << ' ';
    return os;
}

雙向迭代器：新增 `operator--`

template <typename Type>
class ListIterator {
public:
    ListIterator(const DoubleList<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 DoubleListNode<Type> *operator->() const throw(std::out_of_range);
    DoubleListNode<Type> *operator->() throw(std::out_of_range);
    ListIterator &operator++() throw(std::out_of_range);
    ListIterator operator++(int) throw(std::out_of_range);
    ListIterator &operator--();  // 前置--
    ListIterator operator--(int); // 後置--
    bool isEmpty() const { return currentNode == list.first; }

private:
    const DoubleList<Type> &list;
    DoubleListNode<Type> *currentNode;
};

// -- 實現（注意：此版本無邊界檢查，屬教學演示）
template <typename Type>
ListIterator<Type> &ListIterator<Type>::operator--() {
    currentNode = currentNode->prev; return *this;
}
template <typename Type>
ListIterator<Type> ListIterator<Type>::operator--(int) {
    ListIterator tmp(*this); --(*this); return tmp;
}

測試代碼與輸出

int main() {
    DoubleList<int> myList;
    for (int i = 0; i < 3; ++i) myList.push_back(i+1);
    for (int i = 0; i < 5; ++i) myList.push_front(10+i);
    for (int i = 0; i < 3; ++i) myList.push_back(i+1);

    // 正向遍歷
    ListIterator<int> iter(myList);
    while (!iter.isEmpty()) { cout << *iter << ' '; ++iter; }
    cout << endl;

    // 反向遍歷
    ListIterator<int> iter2(myList); ++iter2; --iter2;  // 移到尾部
    while (!iter2.isEmpty()) { cout << *iter2 << ' '; --iter2; }
    cout << endl;

    // 功能測試
    cout << myList << endl;
    myList.insert(1, 14); myList.insert(2, 13); myList.insert(88, 88);
    cout << myList << endl;
    myList.pop_back(); myList.pop_front();
    cout << myList << endl;
    // ... search/remove 交互測試
}