C 語言實現雙向非循環鏈表節點插入：全位置覆蓋 (首中尾統一邏輯)

雙向鏈表插入：四指針操作的藝術

雙向鏈表插入需維護 next 和 prior 兩組指針，涉及 4 個指針賦值。無頭結點版本需分別處理空表插入、首節點前插入、尾節點後插入、中間插入四種情況。本文給出窮盡邊界條件的標準實現。

核心代碼：InsertList

Node* InsertList(Node *head, int pos, int x) {
    // pos: 0-based 位置 (0=首節點前, size=尾部後)
    int size = 0;
    for (Node *p = head; p; p = p->next) size++;
    
    // 1. 合法性檢查
    if (pos < 0 || pos > size) { printf("位置 %d 非法 [0, %d]\n", pos, size); return head; }
    
    // 2. 創建新節點
    Node *pInsert = (Node*)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->element = x;
    pInsert->next = pInsert->prior = NULL;
    
    // 3. 空表插入 (pos 必為 0)
    if (!head && pos == 0) return pInsert;
    
    Node *pMove = head;
    
    // 4. 插入首節點前 (pos == 0)
    if (pos == 0) {
        pInsert->next = head;
        head->prior = pInsert;
        return pInsert; // 新頭節點
    }
    
    // 5. 遍歷到插入位置前驅 (第 pos-1 個節點)
    for (int i = 0; i < pos - 1; i++) pMove = pMove->next;
    
    // 6. 插入尾部 (pos == size)
    if (pos == size) {
        pMove->next = pInsert;
        pInsert->prior = pMove;
        return head;
    }
    
    // 7. 中間插入 (標準四指針操作)
    pInsert->next = pMove->next;
    pMove->next->prior = pInsert; // 關鍵：原後繼節點 prior 指向新節點
    pInsert->prior = pMove;
    pMove->next = pInsert;
    
    return head;
}

四種插入場景圖解

原鏈表: [10] <-> [20] <-> [30]

1. 空表插入 (pos=0, x=5):
[5] -> NULL (prior=NULL, next=NULL)

2. 首節點前插入 (pos=0, x=5):
[5] <-> [10] <-> [20] <-> [30]
  ↑新頭

3. 尾部插入 (pos=3, x=40):
[10] <-> [20] <-> [30] <-> [40]
                      ↑新尾

4. 中間插入 (pos=1, x=15):
[10] <-> [15] <-> [20] <-> [30]
       ↑pMove  ↑pMove->next
四指針操作:
pInsert->next = pMove->next;      // 15->next = 20
pMove->next->prior = pInsert;     // 20->prior = 15 (關鍵!)
pInsert->prior = pMove;           // 15->prior = 10
pMove->next = pInsert;            // 10->next = 15

關鍵操作順序 (中間插入)

1. pInsert->next = pMove->next; (新節點連後繼)
2. pMove->next->prior = pInsert; (後繼回連新節點) **最關鍵，易遺漏**
3. pInsert->prior = pMove; (新節點連前驅)
4. pMove->next = pInsert; (前驅連新節點)

順序原則：**先建立新節點的雙向連接，再修改原節點指針**，減少中斷時的不一致窗口。

對比：單向鏈表插入 vs 雙向鏈表插入

測試驗證

int main() {
    Node *list = NULL;
    list = InsertList(list, 0, 10); // 空表插入: [10]
    list = InsertList(list, 0, 5);  // 首插: [5, 10]
    list = InsertList(list, 2, 20); // 尾插: [5, 10, 20]
    list = InsertList(list, 1, 7);  // 中插: [5, 7, 10, 20]
    list = InsertList(list, 5, 99); // 非法位置
    // 打印驗證...
    return 0;
}

總結

雙向鏈表插入的核心難點在於四指針操作的正確順序與邊界條件的窮盡。無頭結點版本通過分類討論 (空/首/尾/中) 實現全覆蓋。工程實踐中，帶頭結點的循環雙向鏈表 (Linux list_head) 將所有插入統一為「在指定節點前插入」單一操作，消除了所有邊界判斷，是生產級代碼的最佳選擇。