您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

C語言實現雙向非循環鏈表逆序打印：雙向指針優勢的經典展現

編輯：C 語言入門

在《C語言實現單鏈表的逆序打印》中，單鏈表逆序需「構建新鏈表頭插法」或「遞歸/棧輔助」，空間或時間代價較大。而雙向非循環鏈表憑藉 prior 指針，可直接從尾部向前遍歷，實現真正的 O(1) 空間、O(n) 時間逆序打印。本文詳細實現正向與逆序雙模式打印。

節點結構

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

正向打印（標準遍歷）

void PrintList(Node* pHead) {
    if (!pHead) {
        printf("%s: 鏈表為空\n", __FUNCTION__);
        return;
    }
    for (Node* p = pHead; p; p = p->next) {
        printf("%d ", p->element);
    }
    printf("\n%s: 正向打印完成\n", __FUNCTION__);
}

逆序打印（核心算法）

void ReversePrintList(Node* pHead) {
    if (!pHead) {
        printf("%s: 鏈表為空，逆序打印失敗\n", __FUNCTION__);
        return;
    }
    
    // 1. 定位尾節點
    Node* pTail = pHead;
    while (pTail->next) pTail = pTail->next;
    
    // 2. 從尾向前遍歷
    for (Node* p = pTail; p; p = p->prior) {
        printf("%d ", p->element);
    }
    printf("\n%s: 逆序打印成功\n", __FUNCTION__);
}

單/雙向鏈表逆序對比

維度	單鏈表	雙向鏈表
空間複雜度	O(n) 新鏈表/棧/遞歸棧	O(1) 僅需尾指針
時間複雜度	O(n)	O(n)
代碼複雜度	中（需輔助結構）	低直接雙向遍歷
修改原鏈表	頭插法會改變結構	完全不修改

完整測試代碼

Node* CreateList();  // 尾插法建表，輸入正整數以負數結束

int main() {
    Node* list = CreateList();  // 輸入：1 2 3 4 5 -1
    
    PrintList(list);        // 1 2 3 4 5
    ReversePrintList(list); // 5 4 3 2 1
    
    return 0;
}

工程啟示

數據結構選型決策：若業務頻繁需求逆序遍歷、雙向游標移動、快速刪除已知節點，雙向鏈表優於單鏈表。
帶頭尾結點進化：在雙向鏈表基礎上再增加頭尾哨兵節點，可將「定位尾節點」優化為 O(1)，並統一所有邊界條件，是工程級雙向鏈表的標準形態（如 Linux kernel list_head）。

雙向鏈表的逆序打印，生動詮釋了「空間換時間」與「結構決定算法」的核心思想。掌握其遍歷模式，是進階數據結構學習的關鍵一環。