C++ 雙向循環鏈表完整實現：創建、查找、插入、刪除、遍歷

數據結構定義

struct Node {
    char name[20];
    Node* llink;  // 前驅
    Node* rlink;  // 後繼
};

頭節點 head 不存儲數據，head->rlink 指向首節點，head->llink 指向尾節點，首尾相連構成循環。

核心操作實現

1. 創建鏈表

Node* Create(int n) {
    Node* h = new Node;
    h->name[0] = 0; h->llink = h->rlink = nullptr;
    Node* p = h;
    for (int i = 0; i < n; ++i) {
        Node* s = new Node;
        cout << "請輸入第 " << i+1 << " 個人的姓名：";
        cin >> s->name;
        p->rlink = s;
        s->llink = p;
        s->rlink = nullptr;
        p = s;
    }
    p->rlink = h;  // 尾連頭
    h->llink = p;  // 頭連尾
    return h;
}

2. 查找節點

Node* Search(Node* h, const char* name) {
    Node* p = h->rlink;
    for (int i = 0; i < N; ++i) {
        if (strcmp(p->name, name) == 0) return p;
        p = p->rlink;
    }
    return nullptr;  // 未找到
}

3. 插入節點（在 p 之後）

void Insert(Node* p) {
    Node* s = new Node;
    cout << "請輸入要插入的姓名：";
    cin >> s->name;
    Node* r = p->rlink;
    p->rlink = s;
    s->llink = p;
    r->llink = s;
    s->rlink = r;
    ++N;
}

圖解：p → s → r，修改四個指針完成雙向鏈接。

4. 刪除節點

void Delete(Node* p) {
    Node* l = p->llink;
    Node* r = p->rlink;
    l->rlink = r;
    r->llink = l;
    delete p;
    --N;
}

圖解：l → p → r 變為 l → r，釋放 p。

5. 遍歷顯示

void Display(Node* h) {
    Node* p = h->rlink;
    for (int i = 0; i < N; ++i) {
        cout << "第 " << i+1 << " 個人的姓名：" << p->name << endl;
        p = p->rlink;
    }
}

主程序測試

int main() {
    Node* head = Create(10);
    Display(head);

    char strName[20];
    cout << "請輸入要查找的人的姓名: ";
    cin >> strName;
    Node* pSearch = Search(head, strName);
    if (pSearch) {
        cout << "找到：" << pSearch->name << endl;
        Insert(pSearch);
        Display(head);
    }

    cout << "輸入要刪除的姓名: ";
    cin >> strName;
    pSearch = Search(head, strName);
    if (pSearch) {
        Delete(pSearch);
        Display(head);
    }
    return 0;
}

代碼特點與改進方向

• 優點：邏輯清晰，指針操作直觀，適合初學者理解雙向循環鏈表機制。
• 局限：使用全局變量 N 維護長度，非線程安全；未使用模板/類封裝，泛型性差；手動內存管理易泄漏。
• 現代化重構：
  1. 封裝為模板類 CircularDoublyLinkedList<T>。
  2. 使用 std::unique_ptr 或 std::shared_ptr 管理節點生命周期。
  3. 實現迭代器支持範圍 for 循環與 STL 算法。
  4. 提供拷貝/移動語義、异常安全保證。