C語言雙向鏈表頭插法實現詳解與常見錯誤分析

問題描述

使用頭插法建立雙向鏈表時，程式運行結果不正確，無法正確輸入和輸出數據。原代碼存在指針操作邏輯錯誤。

原代碼核心錯誤分析

// 錯誤的插入邏輯
if (L->next = NULL) {  // 這裡用了賦值而非比較！
    L->next = p;
    p->prior = L;
    p->next = NULL;
} else {
    p->next = L->next;
    p->prior = L;          // 錯誤：所有新節點的 prior 都指向頭節點 L
    L->next->prior = p;
    L->next = p;           // 錯誤：L->next 永遠指向最新節點，導致鏈表斷裂
}

三個致命錯誤

1. if (L->next = NULL) 使用賦值運算符 = 而非比較運算符 ==
2. 新節點的 prior 全部指向頭節點 L，而非前一個節點
3. 頭節點 L->next 永遠指向最新插入節點，丟失了之前的節點鏈接

正確的頭插法實現

states create(DuLinkList &L) {
    DuLinkList p, tail = NULL;
    L = (DuLinkList)malloc(sizeof(DuLNode));
    L->next = NULL;
    L->prior = NULL;
    
    printf("請輸入鏈表長度：\n");
    int n; scanf("%d", &n);
    
    for (int i = n; i > 0; i--) {
        p = (DuLinkList)malloc(sizeof(DuLNode));
        printf("請輸入第 %d 個元素的值：\n", i);
        scanf("%d", &p->data);
        
        // 正確的頭插法邏輯
        p->next = L->next;
        p->prior = L;
        if (L->next != NULL) {
            L->next->prior = p;
        }
        L->next = p;
        
        // 維護尾指針（可選，用於反向遍歷）
        if (tail == NULL) tail = p;
    }
    return OK;
}

關鍵點總結

• 頭插法：新節點插在頭節點之後，L->next 指向新節點
• 雙向鏈表必須維護 prior 和 next 兩個方向的指針
• 插入時順序：先處理新節點的指針，再更新相鄰節點的指針
• 尾插法需維護尾指針 tail，頭插法不需要

完整可運行代碼

包含創建、打印、主函數的完整實現，已在 Linux 環境測試通過。