C 語言實現雙向非循環鏈表 (無頭結點)：構建、正向遍歷完整指南

編輯：關於C語言

雙向鏈表：前驅後繼雙指針，操作靈活的代價

雙向非循環鏈表每個節點擁有 prior (前驅) 和 next (後繼) 兩個指針，支持雙向遍歷、O(1) 刪除已知節點、逆序輸出等優勢。無頭結點版本構建時需同步維護雙向指針，邊界條件較單向鏈表複雜。

節點定義

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

尾插法構建 `createList` (順序構建)

Node* createList(Node *head) {
    Node *pInsert, *pMove = head;
    
    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 (!head) { head = pInsert; pMove = head; }
        else {
            pMove->next = pInsert;      // 前驅指向新節點
            pInsert->prior = pMove;     // 新節點指向前驅 (關鍵雙向鏈接)
            pMove = pMove->next;        // 移動尾指針
        }
        pInsert = (Node*)malloc(sizeof(Node));
        memset(pInsert, 0, sizeof(Node));
        pInsert->next = pInsert->prior = NULL;
        scanf("%d", &pInsert->element);
    }
    free(pInsert);
    return head;
}

正向打印 `printList`

void printList(Node *head) {
    if (!head) { printf("鏈表為空\n"); return; }
    while (head) { printf("%d ", head->element); head = head->next; }
    printf("\n");
}

關鍵點：雙向鏈接順序


操作單向鏈表雙向鏈表


節點結構nextprior + next
尾插鏈接1 步2 步 (雙向)
空表初始化head = pInserthead = pInsert; pMove = head
逆序遍歷需額外空間/反轉原生支持 (prior)
已知節點刪除O(n) 找前驅O(1) 直接斷開



測試主函數
int main() {
    Node *list = NULL;
    printf("輸入數據 (>0 構建): ");
    list = createList(list); // 例: 10 20 30 0
    printf("正向輸出: ");
    printList(list); // 10 20 30
    // 內存釋放略
    return 0;
}

總結
雙向非循環鏈表構建的核心在於同步維護 prior/next 兩個指針。尾插法中「原尾 next 指向新節點、新節點 prior 指向原尾」是標準雙向鏈接模式。無頭結點版本需額外處理首節點 prior=NULL、尾指針維護。工程中強烈建議使用帶頭結點的雙向循環鏈表 (如 Linux kernel list_head)，可將首尾邊界統一，代碼量減半、健壯性大增。