C 語言構建非循環雙向鏈表：頭插法與尾插法完整實現（無頭結點）

雙向鏈表創建的兩種經典範式

雙向鏈表因擁有 prior 和 next 兩個指針，操作靈活性遠超單向鏈表。無頭結點的非循環雙向鏈表創建時，需妥善處理首節點的雙向指針初始化（均為 NULL）以及後續節點的雙向鏈接。本文對比實現尾插法（保持輸入順序）與頭插法（逆序輸入）兩種構建策略。

核心數據結構

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

尾插法 TailInsertCreateList：順序構建

核心邏輯：維護 pMove 指向當前尾節點，新節點 pInsert 掛在尾部，並雙向鏈接。

Node *TailInsertCreateList(Node *pNode) {
    Node *pInsert, *pMove = NULL;
    pInsert = (Node*)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->next = pInsert->prior = NULL;
    scanf("%d", &(pInsert->element));

    if (pInsert->element <= 0) { free(pInsert); return NULL; }

    while (pInsert->element > 0) {
        if (pNode == NULL) {          // 首節點
            pNode = pInsert;
            pMove = pNode;
        } else {                      // 尾插並雙向鏈接
            pMove->next = pInsert;
            pInsert->prior = pMove;
            pMove = pMove->next;      // pMove 移動到新尾部
        }
        // 準備下一節點
        pInsert = (Node*)malloc(sizeof(Node));
        memset(pInsert, 0, sizeof(Node));
        pInsert->next = pInsert->prior = NULL;
        scanf("%d", &(pInsert->element));
    }
    free(pInsert); // 釋放最後多分配的節點
    return pNode;
}

頭插法 HeadInsertCreateList：逆序構建

核心邏輯：新節點永遠插在頭部，原頭節點變為第二個節點，需更新原頭節點的 prior 指向新頭。

Node *HeadInsertCreateList(Node *pNode) {
    Node *pInsert;
    pInsert = (Node*)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->next = pInsert->prior = NULL;
    scanf("%d", &(pInsert->element));

    if (pInsert->element <= 0) { free(pInsert); return NULL; }

    while (pInsert->element > 0) {
        if (pNode == NULL) {          // 首節點
            pNode = pInsert;
        } else {                      // 頭插並雙向鏈接
            pInsert->next = pNode;
            pNode->prior = pInsert;
            pNode = pInsert;          // 頭指針前移
        }
        // 準備下一節點
        pInsert = (Node*)malloc(sizeof(Node));
        memset(pInsert, 0, sizeof(Node));
        pInsert->next = pInsert->prior = NULL;
        scanf("%d", &(pInsert->element));
    }
    free(pInsert);
    return pNode;
}

關鍵差異對比表

內存管理細節

• 循環中每次 malloc 後立即 memset 清零，避免野指針。
• 循環結束後，最後一次讀取失敗（輸入 ≤ 0）導致多分配一個節點，需顯式 free(pInsert) 釋放。
• 實際工程中應檢查 malloc 返回值，防止 OOM。

總結

頭插法與尾插法是鏈表構建的兩大基石。雙向鏈表相比單向鏈表，在插入時額外維護了 prior 指針，但邏輯同樣清晰：尾插法維護尾指針順向生長，頭插法移動頭指針逆向生長。理解這兩種模式，是掌握 LRU Cache、雙端隊列、文本編輯器緩衝區等高級數據結構的前置知識。