單鏈表逆序打印需 O(n) 額外空間 (構建新鏈表/棧/數組) 或修改指針。而雙向鏈表憑藉 prior 指針，可直接從尾部向前遍歷，實現真正的 O(1) 空間、O(n) 時間逆序輸出。這是雙向鏈表相比單向鏈表最直觀的優勢體現。
next 直到 pMove->next == NULL，定位尾節點。prior 向前遍歷打印，直到 pMove == NULL (越過頭節點)。#include#include #include typedef struct Node { int element; struct Node *prior; struct Node *next; } Node; // 尾插構建 (同上篇) 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 = pInsert; } pInsert = (Node*)malloc(sizeof(Node)); memset(pInsert, 0, sizeof(Node)); pInsert->next = pInsert->prior = NULL; scanf("%d", &pInsert->element); } free(pInsert); return head; } // 正向打印 void printList(Node *head) { if (!head) { printf("空\n"); return; } while (head) { printf("%d ", head->element); head = head->next; } printf("\n"); } // 核心：逆序打印 void ReversePrintList(Node *head) { if (!head) { printf("鏈表為空\n"); return; } Node *pMove = head; // 1. 正向遍歷到尾節點 while (pMove->next) pMove = pMove->next; // 2. 逆向遍歷打印 printf("逆序輸出: "); while (pMove) { printf("%d ", pMove->element); pMove = pMove->prior; } printf("\n"); } int main() { Node *list = NULL; printf("輸入數據: "); list = createList(list); // 1 2 3 4 5 0 printf("正向: "); printList(list); // 1 2 3 4 5 ReversePrintList(list); // 逆序輸出: 5 4 3 2 1 return 0; }
輸入數據: 10 20 30 40 50 0 正向: 10 20 30 40 50 逆序輸出: 50 40 30 20 10
| 指標 | 單向鏈表 (構建新鏈表法) | 雙向鏈表 (原生 prior) |
|---|---|---|
| 時間 | O(n) | O(n) |
| 額外空間 | O(n) (新節點/棧/數組) | O(1) (僅指針變量) |
| 代碼複雜度 | 中 (分配/鏈接/釋放) | 極低 (兩輪遍歷) |
| 修改原結構 | 否 (構建新表) | 否 |
若使用帶頭結點的循環雙向鏈表：
// 逆序遍歷宏 (Linux kernel 風格)
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
// 使用:
struct list_head *pos;
list_for_each_prev(pos, &head) {
MyNode *node = list_entry(pos, MyNode, list);
printf("%d ", node->data);
}
// 無需「找尾」階段，頭結點 prev 直接指向尾節點，代碼更優雅。
雙向鏈表逆序打印完美展示了「空間換時間」的反面：**用優勢結構特性 (prior 指針) 換取算法極致簡潔**。無頭結點版本只需兩輪遍歷 (找尾 + 逆向打印)，帶頭結點循環版本更是一輪宏搞定。這也是為什麼 Linux 內核、C++ STL list、數據庫雙向鏈表索引都選擇雙向結構的核心原因：對稱性帶來的操作統一性與效率。
