C 語言實現帶頭尾節點的雙向非循環鏈表：任意位置插入元素完整指南

為什麼選擇「帶頭尾節點」的雙向鏈表？

在《C語言實現雙向非循環鏈表（不帶頭結點）的節點插入》中我們已見識過無頭節點版本的繁瑣邊界判斷。引入虛擬頭節點與虛擬尾節點後，插入邏輯統一化：無需特別處理「插入頭部」「插入尾部」「空鏈表」等特例，代碼更簡潔、健壯。

數據結構定義

typedef struct Node {
    int element;              // 數據域
    struct Node *prior;       // 前驅指針
    struct Node *next;        // 後繼指針
} Node;

初始化時：pHead->next = pTail; pTail->prior = pHead; pHead->prior = pTail->next = NULL;

核心插入算法：InsertNodeList

// 在位置 pos (0-based) 插入值 x，成功返回 1，失敗返回 0
int InsertNodeList(Node *pHead, Node *pTail, int pos, int x) {
    Node *pMove = pHead;
    int i = 0;

    // 遍歷到插入位置的前一個節點
    while (pMove != pTail) {
        if (i == pos) break;
        i++;
        pMove = pMove->next;
    }

    // pos 超出合法範圍（> 當前長度）
    if (pMove == pTail) {
        printf("%s: 插入失敗，pos=%d 越界\n", __FUNCTION__, pos);
        return 0;
    }

    // 分配新節點
    Node *pInsert = (Node *)malloc(sizeof(Node));
    if (!pInsert) return 0;                 // 內存不足
    pInsert->element = x;
    pInsert->prior = pInsert->next = NULL;

    // 四步鏈接，順序關鍵！
    pMove->next->prior = pInsert;           // 1. 後節點前驅指向新節點
    pInsert->next = pMove->next;            // 2. 新節點後繼指向後節點
    pMove->next = pInsert;                  // 3. 前節點後繼指向新節點
    pInsert->prior = pMove;                 // 4. 新節點前驅指向前節點

    printf("%s: 在 pos=%d 插入 x=%d 成功\n", __FUNCTION__, pos, x);
    return 1;
}

鏈接順序為何如此重要？

1. 先斷開後節點的 prior，避免丟失後續鏈表；
2. 建立新節點的 next；
3. 建立前節點的 next；
4. 最後建立新節點的 prior。

任何順序錯誤都可能導致鏈表斷裂或指針指向錯誤內存。

完整測試主程序

int main() {
    Node *pHead = (Node *)malloc(sizeof(Node));
    Node *pTail = (Node *)malloc(sizeof(Node));
    pHead->next = pTail;  pTail->prior = pHead;
    pHead->prior = pTail->next = NULL;

    InsertNodeList(pHead, pTail, 0, 10);  // 10
    InsertNodeList(pHead, pTail, 1, 20);  // 10 20
    InsertNodeList(pHead, pTail, 1, 15);  // 10 15 20
    InsertNodeList(pHead, pTail, 3, 30);  // 10 15 20 30

    // 正向遍歷驗證
    for (Node *p = pHead->next; p != pTail; p = p->next)
        printf("%d ", p->element);        // 輸出: 10 15 20 30
    printf("\n");

    // 反向遍歷驗證 prior 指針
    for (Node *p = pTail->prior; p != pHead; p = p->prior)
        printf("%d ", p->element);        // 輸出: 30 20 15 10
    printf("\n");

    // 釋放內存略
    return 0;
}

常見錯誤與調試技巧

進階擴展

• 尾插優化：維護 size 變量，pos == size 直接尾插 O(1)。
• 雙向迭代器：封裝 begin()/end()/rbegin()/rend() 模擬 STL 風格。
• 線程安全：加入讀寫鎖，實現多線程安全版本。

完整代碼已上傳 GitHub：InsertNodeDoubleLinkedList_HeadNode，歡迎 Star & Fork！