C語言實現雙向鏈表：完整代碼、圖解操作與常見錯誤避坑指南

數據結構定義

[cpp]
typedef struct DNode {
    struct DNode *prev;
    struct DNode *next;
    int data;
} DNode;

雙向鏈表每個節點包含前驅指針、後繼指針與數據域。本文實現帶頭節點的非循環雙向鏈表，頭節點不存儲有效數據，head->next 指向首元節點，head->prev = NULL。

核心操作實現

1. 初始化頭節點

[cpp]
DNode* init(int data) {  // data 可作為頭節點標識或首元值
    DNode *head = (DNode*)malloc(sizeof(DNode));
    if (!head) exit(EXIT_FAILURE);
    head->prev = NULL;
    head->next = NULL;
    head->data = data;
    return head;
}

2. 尾插法（O(1) 需維護尾指針，此處為教學簡化 O(n)）

[cpp]
void insertLastNode(DNode *head, int data) {
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->next = NULL;

    // 找到尾節點
    DNode *cur = head;
    while (cur->next) cur = cur->next;

    cur->next = newNode;
    newNode->prev = cur;
}

3. 指定位置插入（在值為 data 的節點之前插入）

[cpp]
// 找前驅節點
DNode* findPrev(DNode *head, int data) {
    DNode *cur = head;
    while (cur->next && cur->next->data != data)
        cur = cur->next;
    return cur;  // 可能是尾節點（未找到）
}

void insertNode(DNode *head, int data) {
    DNode *prev = findPrev(head, data);
    if (!prev->next) return;  // 未找到目標節點

    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = data;

    newNode->next = prev->next;
    newNode->prev = prev;
    prev->next->prev = newNode;  // 關鍵：原後繼節點的 prev 指向新節點
    prev->next = newNode;
}

4. 刪除指定值節點

[cpp]
DNode* findCur(DNode *head, int data) {
    DNode *cur = head->next;
    while (cur && cur->data != data) cur = cur->next;
    return cur;
}

void deleteNode(DNode *head, int data) {
    DNode *target = findCur(head, data);
    if (!target) return;  // 未找到

    if (target->next) {          // 非尾節點
        target->next->prev = target->prev;
    }
    target->prev->next = target->next;  // 統一處理：前驅的 next 跳過 target
    free(target);
}

圖解：插入與刪除指針變化

圖示：雙向鏈表插入/刪除時四個指針的重連順序，切記「先連外再連內」或「先斷後連」原則，避免斷鏈。

常見錯誤與修正

完整可運行測試主函數

[cpp]
int main() {
    DNode *list = init(0);  // 頭節點 data=0 作為標識
    insertLastNode(list, 10);
    insertLastNode(list, 20);
    insertLastNode(list, 30);
    insertNode(list, 20);   // 在 20 前插入 20（演示）
    deleteNode(list, 20);   // 刪除第一個 20

    // 遍歷輸出
    for (DNode *p = list->next; p; p = p->next)
        printf("%d ", p->data);
    // 輸出: 10 20 30

    // 釋放鏈表
    DNode *cur = list->next;
    while (cur) {
        DNode *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    free(list);
    return 0;
}

進階優化建議

• 維護 尾指針 實現 O(1) 尾插。
• 改為循環雙向鏈表（head->prev = tail），統一邊界條件，代碼更簡潔。
• 封裝為泛型容器（用 void* 存數據 + 銷毀回調函數）。
• 多線程環境下加讀寫鎖或使用無鎖數據結構。