您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

C語言實現雙向非循環鏈表（無頭結點）節點插入完整算法

編輯：C 語言入門

延續《C語言實現雙向非循環鏈表的逆序打印》，本文攻克雙向非循環鏈表（無頭結點）的通用位置插入算法。相比單鏈表，雙向鏈表插入需同時維護 next 與 prior 兩個指針域，且無頭結點時首節點、尾節點、中間節點、空鏈表四種邊界情況需分別處理，邏輯較繁瑣但極具訓練價值。

節點定義與輔助函數

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

int SizeList(Node* head);  // 獲取鏈表長度（遍歷計數）

通用插入函數

Node* InsertList(Node* pHead, int pos, int x) {
    // pos: 0-based 索引，0=首節點前，size=尾部後
    int size = SizeList(pHead);
    if (pos < 0 || pos > size) {
        printf("%s: pos=%d 非法（範圍 0~%d）\n", __FUNCTION__, pos, size);
        return pHead;
    }
    
    Node* pInsert = (Node*)malloc(sizeof(Node));
    if (!pInsert) return pHead;
    pInsert->element = x;
    pInsert->prior = pInsert->next = NULL;
    
    // 情況1：空鏈表且插入位置為0
    if (!pHead && pos == 0) {
        printf("%s: 空鏈表首插 pos=0 x=%d 成功\n", __FUNCTION__, x);
        return pInsert;  // 新節點成為頭節點
    }
    
    Node* pMove = pHead;
    
    // 情況2：插入首節點（pos==0）
    if (pos == 0) {
        pInsert->next = pHead;
        pHead->prior = pInsert;
        printf("%s: 首節點前插入 x=%d 成功\n", __FUNCTION__, x);
        return pInsert;  // 新頭節點
    }
    
    // 情況3：插入尾部（pos==size）
    if (pos == size) {
        while (pMove->next) pMove = pMove->next;  // 定位尾節點
        pMove->next = pInsert;
        pInsert->prior = pMove;
        printf("%s: 尾部插入 x=%d 成功\n", __FUNCTION__, x);
        return pHead;
    }
    
    // 情況4：中間插入（1 <= pos < size）
    for (int i = 1; pMove; i++) {
        if (i == pos) {
            // 關鍵：指針連接順序決定成敗
            pInsert->next = pMove->next;
            pMove->next->prior = pInsert;  // 後節點的 prior 指向新節點
            pInsert->prior = pMove;
            pMove->next = pInsert;
            printf("%s: 中間插入 pos=%d x=%d 成功\n", __FUNCTION__, pos, x);
            break;
        }
        pMove = pMove->next;
    }
    return pHead;
}

指針連接順序圖解（中間插入）

插入前:  ... <-> A <-> B <-> ...
目標:    在 A 後、B 前插入 X (pos 指向 B 的位置)

正確順序:
1. X->next = B
2. B->prior = X
3. X->prior = A
4. A->next = X

結果:    ... <-> A <-> X <-> B <-> ...

關鍵難點總結

難點	解決策略
無頭結點首節點特判	pos==0 時返回新頭指針，調用者必須接收返回值
尾節點插入需遍歷	pos==size 時單獨處理，避免進入中間插入邏輯導致 pMove->next 為 NULL 解引用
四指針連接順序	先連新節點的 next/prior，再修改鄰居節點指針，防止斷鏈
空鏈表合法性	僅允許 pos==0，其他位置直接報錯

測試驗證

int main() {
    Node* list = NULL;
    list = InsertList(list, 0, 10);  // 空鏈表首插 -> 10
    list = InsertList(list, 1, 20);  // 尾插 -> 10 20
    list = InsertList(list, 1, 15);  // 中間插 -> 10 15 20
    list = InsertList(list, 0, 5);   // 新頭 -> 5 10 15 20
    list = InsertList(list, 4, 25);  // 新尾 -> 5 10 15 20 25
    PrintList(list);
    return 0;
}

雙向鏈表插入算法是指針操作綜合能力的試金石。建議讀者在紙上反覆推演四種邊界情況的指針變化，直到能盲寫無誤。實際工程中，強烈建議使用帶頭尾結點的雙向鏈表，可將邊界情況從 4 種減至 1 種，大幅降低認知負荷與 Bug 率。