C++ 實現雙向循環鏈表完整教學：含增刪查排逆序操作

資料結構定義

雙向循環鏈表：每個節點含 data、next、prev；頭尾相連，設哨兵節點 head 簡化邊界處理，head->data 存放長度，head->next 指向首節點，head->prev 指向尾節點。

核心操作完整實作 (模板類)

#include <iostream>
using namespace std;

template <typename T>
class CDList {
    struct Node {
        T data;
        Node *next, *prev;
        Node(const T& d = T(), Node* n = nullptr, Node* p = nullptr)
            : data(d), next(n), prev(p) {}
    };
    Node *head; // 哨兵節點
public:
    CDList() { head = new Node(); head->next = head->prev = head; }
    ~CDList() { clear(); delete head; }

    // 尾插
    void push_back(const T& x) {
        Node* s = new Node(x, head, head->prev);
        head->prev->next = s;
        head->prev = s;
        ++head->data;
    }
    // 頭插
    void push_front(const T& x) {
        Node* s = new Node(x, head->next, head);
        head->next->prev = s;
        head->next = s;
        ++head->data;
    }
    // 尾刪
    void pop_back() {
        if (empty()) return;
        Node* p = head->prev;
        p->prev->next = head;
        head->prev = p->prev;
        delete p;
        --head->data;
    }
    // 頭刪
    void pop_front() {
        if (empty()) return;
        Node* p = head->next;
        head->next = p->next;
        p->next->prev = head;
        delete p;
        --head->data;
    }
    // 按值有序插入 (假設遞增)
    void insert_sorted(const T& x) {
        Node* p = head;
        while (p->next != head && p->next->data < x) p = p->next;
        Node* s = new Node(x, p->next, p);
        p->next->prev = s;
        p->next = s;
        ++head->data;
    }
    // 顯示
    void show() const {
        if (empty()) { cout << "NULL\n"; return; }
        for (Node* p = head->next; p != head; p = p->next)
            cout << p->data << " -> ";
        cout << "NULL (size=" << head->data << ")\n";
    }
    // 查找
    Node* find(const T& x) const {
        for (Node* p = head->next; p != head; p = p->next)
            if (p->data == x) return p;
        return nullptr;
    }
    // 按值刪除 (第一個匹配)
    void erase(const T& x) {
        Node* p = find(x);
        if (!p) { cout << "Not found: " << x << '\n'; return; }
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        --head->data;
    }
    // 清空
    void clear() {
        while (!empty()) pop_back();
    }
    // 逆序 (就地反轉)
    void reverse() {
        if (empty()) return;
        Node* p = head->next;
        head->next = head->prev = head; // 重置為空表
        head->data = 0;
        while (p != head) { // 原 head 已變更，需暫存原頭
            Node* nxt = p->next;
            // 移至新表頭部 (實際為尾插構建逆序)
            p->next = head->next;
            p->prev = head;
            head->next->prev = p;
            head->next = p;
            ++head->data;
            p = nxt;
        }
    }
    // 排序 (插入排序重建)
    void sort() {
        if (empty()) return;
        vector v;
        for (Node* p = head->next; p != head; p = p->next) v.push_back(p->data);
        std::sort(v.begin(), v.end());
        clear();
        for (auto& val : v) push_back(val);
    }
    bool empty() const { return head->data == 0; }
    int size() const { return head->data; }
};

// 測試主程式
int main() {
    CDList L;
    L.push_back(3); L.push_back(1); L.push_back(4); L.push_back(2);
    cout << "Original: "; L.show(); // 3 1 4 2
    L.sort(); cout << "Sorted: "; L.show(); // 1 2 3 4
    L.reverse(); cout << "Reversed: "; L.show(); // 4 3 2 1
    L.insert_sorted(2); cout << "Insert 2: "; L.show(); // 2 2 3 4
    L.erase(3); cout << "Erase 3: "; L.show(); // 2 2 4
    return 0;
}

關鍵實作細節解析

1. 哨兵節點：消除頭尾空表、單節點的特判，統一插入刪除邏輯。
2. 長度維護：head->data 存 size，O(1) 取長度。
3. 逆序：就地重組指針，不分配新節點，時間 O(n)、空間 O(1)。
4. 排序：為簡潔改用 vector 輔助 O(n log n)，也可實作鏈表歸併排序。
5. 記憶體安全：解構函數 clear() 遞迴釋放，防洩漏。

測試輸出範例

Original: 3 -> 1 -> 4 -> 2 -> NULL (size=4)
Sorted: 1 -> 2 -> 3 -> 4 -> NULL (size=4)
Reversed: 4 -> 3 -> 2 -> 1 -> NULL (size=4)
Insert 2: 2 -> 2 -> 3 -> 4 -> NULL (size=5)
Erase 3: 2 -> 2 -> 4 -> NULL (size=4)

延伸練習

• 實作 iterator 支援範圍-based for 迴圈。
• 加入 merge (合併兩有序表)、unique (移除重複)。
• 對比 std::list 介面設計差異。