C 語言實現非循環雙向鏈表節點刪除（無頭結點版）完整指南

雙向鏈表刪除操作的邊界條件藝術

無頭結點的非循環雙向鏈表在刪除節點時，需同時維護 prior（前驅）與 next（後繼）兩個指針，且必須單獨處理首節點、尾節點、唯一節點三種邊界情況，邏輯較單向鏈表複雜。本文提供兩種刪除模式的完整實現：按位置刪除與按值刪除。

核心數據結構

typedef struct Node {
    int element;
    struct Node *prior;
    struct Node *next;
} Node;

場景一：按位置刪除 deletePosList

關鍵邏輯分層：

1. 空表檢查：pNode == NULL 直接返回。
2. 單節點刪除首位：pos==1 && size==1，釋放節點並返回 NULL。
3. 多節點刪除首位：pos==1，頭指針後移，新首節點 prior=NULL，釋放舊首節點。
4. 中間節點刪除：pos != size，斷開雙向連結 pMove->prior->next = pMove->next; pMove->next->prior = pMove->prior;。
5. 尾節點刪除：pos == size，前驅節點 next=NULL，釋放尾節點。

場景二：按值刪除 deleteValueList

邏輯結構類似，但遍歷條件變為 pMove->element == x。同樣需分別處理：

• 首節點且長度為 1
• 首節點且長度 > 1
• 中間節點
• 尾節點

完整代碼實現（含詳細註釋）

// 輔助函數：獲取鏈表長度
int sizeList(Node *pNode) {
    int count = 0;
    while (pNode) { count++; pNode = pNode->next; }
    return count;
}

// 刪除 pos 位置節點
Node *deletePosList(Node *pNode, int pos) {
    if (!pNode) { printf("鏈表為空\n"); return NULL; }
    int size = sizeList(pNode);
    if (pos < 1 || pos > size) { printf("位置非法\n"); return pNode; }

    Node *pMove = pNode;
    int i = 1;

    // 情況 1：刪除唯一節點
    if (size == 1) {
        free(pNode);
        return NULL;
    }

    // 情況 2：刪除首節點
    if (pos == 1) {
        pNode = pNode->next;
        pNode->prior = NULL;
        free(pMove);
        return pNode;
    }

    // 遍歷至目標位置
    while (pMove && i < pos) {
        pMove = pMove->next;
        i++;
    }

    // 情況 3：刪除尾節點
    if (pMove->next == NULL) {
        pMove->prior->next = NULL;
        free(pMove);
        return pNode;
    }

    // 情況 4：刪除中間節點
    pMove->prior->next = pMove->next;
    pMove->next->prior = pMove->prior;
    free(pMove);
    return pNode;
}

// 刪除值為 x 的首個節點
Node *deleteValueList(Node *pNode, int x) {
    if (!pNode) return NULL;
    Node *pMove = pNode;

    while (pMove) {
        if (pMove->element == x) {
            // 唯一節點
            if (pMove->prior == NULL && pMove->next == NULL) {
                free(pMove); return NULL;
            }
            // 首節點
            if (pMove->prior == NULL) {
                pNode = pMove->next;
                pNode->prior = NULL;
                free(pMove);
                return pNode;
            }
            // 尾節點
            if (pMove->next == NULL) {
                pMove->prior->next = NULL;
                free(pMove);
                return pNode;
            }
            // 中間節點
            pMove->prior->next = pMove->next;
            pMove->next->prior = pMove->prior;
            free(pMove);
            return pNode;
        }
        pMove = pMove->next;
    }
    printf("值 %d 不存在\n", x);
    return pNode;
}

避坑指南與最佳實踐

• 指針斷開順序：先斷開鏈表連結，再 free，防止野指針訪問。
• 頭指針更新：刪除首節點時，必須返回新頭指針，調用端需接收返回值（head = deletePosList(head, 1)）。
• 雙向一致性：任何修改 next 都必須同步修改對應節點的 prior，反之亦然。
• 帶頭結點優勢：實際工程中強烈建議使用帶頭結點的雙向鏈表，可統一首尾邏輯，代碼量減少 40% 以上。

總結

無頭結點雙向鏈表刪除操作的核心難點在於邊界條件的窮盡處理。通過分類討論（空表、單節點、首節點、尾節點、中間節點），配合嚴謹的指針操作順序，可構建健壯的刪除函數。掌握此邏輯，有助於深入理解 Linux 內核 list_head、C++ STL list 等高級容器的底層實現原理。