雙向循環鏈表核心操作：插入與刪除完整實現

前言

雙向循環鏈表結合了「雙向指標」與「首尾相連」特性，使節點操作更靈活。本文詳細解析插入與刪除操作的指標調整邏輯，提供可直接運行的C++完整代碼。

一、節點結構定義

typedef struct dnode {
    int data;
    struct dnode *preNode;   // 前驅指標
    struct dnode *nextNode;  // 後繼指標
} dCycleLink;

二、插入操作：指定位置插入新節點

核心邏輯（四步指標重連）

在 p 節點後插入新節點 s：

1. s->preNode = p; // 新節點前驅指向 p
2. p->nextNode->preNode = s; // p原後繼的前驅指向 s
3. s->nextNode = p->nextNode; // 新節點後繼指向 p原後繼
4. p->nextNode = s; // p的後繼指向新節點

完整函數實現

dCycleLink* insertData(dCycleLink *head, int pos, int data) {
    assert(head != NULL);
    dCycleLink *p = head;
    int count = 1;

    // 1. 定位到第 pos 個節點
    while (p != NULL && count < pos) {
        count++;
        p = p->nextNode;
    }

    if (count == pos && p != NULL) {
        // 2. 創建新節點
        dCycleLink *s = (dCycleLink*)malloc(sizeof(dCycleLink));
        if (s != NULL) {
            s->data = data;
            
            // 3. 四步指標重連（核心）
            s->preNode = p;                    // 步驟1
            p->nextNode->preNode = s;          // 步驟2
            s->nextNode = p->nextNode;         // 步驟3
            p->nextNode = s;                   // 步驟4
            
            printf("插入成功！！！\n");
        }
    } else {
        printf("插入失敗：位置越界！！！\n");
    }
    return head;
}

三、刪除操作：按值刪除節點

核心邏輯（雙向斷鏈+釋放）

刪除節點 p：

1. p->preNode->nextNode = p->nextNode; // 前驅跳過 p 指向後繼
2. p->nextNode->preNode = p->preNode; // 後繼跳過 p 指向前驅
3. free(p); p = NULL; // 釋放記憶體

完整函數實現

dCycleLink* deleteData(dCycleLink* head, int data) {
    assert(head != NULL);
    dCycleLink* p = head;

    // 1. 查找目標節點
    while (p != NULL && p->data != data) {
        p = p->nextNode;
    }

    if (p->data == data) {  // 找到目標
        // 2. 雙向斷鏈（核心）
        p->preNode->nextNode = p->nextNode;
        p->nextNode->preNode = p->preNode;
        
        free(p);
        p = NULL;
        printf("找到目標，刪除成功！\n");
    } else {
        printf("未找到目標值，刪除失敗！\n");
    }
    return head;
}

四、輔助函數：創建與列印

創建雙向循環鏈表

dCycleLink* createDoublyCycleLink(int n) {
    int xValue;
    dCycleLink *head, *p, *pre;

    printf("請輸入第1個數字：");
    scanf("%d", &xValue);
    
    p = (dCycleLink*)malloc(sizeof(dCycleLink));
    p->data = xValue;
    p->preNode = NULL;
    p->nextNode = NULL;
    head = p;
    pre = p;

    for (int i = 1; i < n; i++) {
        printf("請輸入第%d個數字：", i+1);
        scanf("%d", &xValue);
        
        p = (dCycleLink*)malloc(sizeof(dCycleLink));
        p->data = xValue;
        p->nextNode = NULL;
        
        p->preNode = pre;      // 體現雙向特性
        pre->nextNode = p;
        pre = p;
    }
    
    // 注意：此處未閉環，若需循環需補上 head->preNode = pre; pre->nextNode = head;
    return head;
}

列印鏈表

void printCycleLink(dCycleLink *head) {
    dCycleLink* pNode = head;
    printf("鏈表數據：\n");
    while (pNode) {
        printf("%d ", pNode->data);
        pNode = pNode->nextNode;
    }
    printf("\n");
}

五、測試主程式

int main() {
    int num;
    printf("請輸入節點個數：");
    scanf("%d", &num);
    
    dCycleLink* list = createDoublyCycleLink(num);
    printCycleLink(list);
    
    list = insertData(list, 2, 10);  // 第2個位置插入10
    list = deleteData(list, 2);      // 刪除值為2的節點
    
    return 0;
}

六、關鍵點總結

雙向循環鏈表的優勢在於：既可正向遍歷也可逆向遍歷，插入刪除只需調整相鄰指標，無需從頭查找前驅節點。掌握指標調整的「四步法」（插入）與「雙向斷鏈」（刪除）是攻克此類問題的關鍵。