清空雙向非循環鏈表時，可利用 prior 指針從頭向後遍歷，逐個釋放前驅節點，最後釋放尾節點。無頭結點版本需處理空表、單節點等邊界。本文提供迭代法與遞歸法兩種實現，並分析優劣。
Node* ClearDoubleLinkedList(Node *head) {
if (!head) { printf("原鏈表已為空\n"); return NULL; }
Node *cur = head;
// 遍歷釋放前驅節點
while (cur->next) {
cur = cur->next; // 移動到下一個
free(cur->prior); // 釋放前一個
cur->prior = NULL; // 斷開回連 (防野指針)
}
// 釋放最後一個節點 (尾節點)
free(cur);
printf("雙向鏈表清空完成\n");
return NULL;
}
void ClearRecursive(Node *node) {
if (!node) return;
ClearRecursive(node->next);
free(node);
}
// 調用:
ClearRecursive(head);
head = NULL;
// 注意: 長鏈表會棧溢出，生產環境禁用
原鏈表: [10] <-> [20] <-> [30] <-> NULL
head
步驟 1: cur=head(10), cur->next 存在
cur = cur->next => cur 指向 20
free(cur->prior) => 釋放 10
cur->prior = NULL => 20->prior = NULL
步驟 2: cur=20, cur->next 存在
cur = cur->next => cur 指向 30
free(cur->prior) => 釋放 20
cur->prior = NULL => 30->prior = NULL
步驟 3: cur=30, cur->next == NULL (循環結束)
free(cur) => 釋放 30
返回 NULL
| 要點 | 說明 |
|---|---|
| 遍歷方向 | 必須從頭向尾 (沿 next)，利用 prior 釋放已訪問節點 |
| 尾節點處理 | 循環結束時 cur 指向尾節點，需額外 free(cur) |
| 斷開指針 | cur->prior = NULL 防止釋放後內存被誤訪問 (好習慣) |
| 返回值 | 返回 NULL 表示鏈表已銷毀，調用端應接收: head = Clear(head) |
| 帶頭結點版 | 從 head->next 開始，保留 head 節點，邏輯類似 |
| 方式 | 單向鏈表 | 雙向鏈表 |
|---|---|---|
| 迭代釋放 | 需保存 next: next = cur->next; free(cur); cur = next; | 利用 prior: cur = cur->next; free(cur->prior); |
| 代碼簡潔度 | 略繁 | 更直觀 |
| 遞歸風險 | 同 (棧溢出) | 同 |
int main() {
Node *list = NULL;
list = createList(list); // 10 20 30 0
printList(list); // 10 20 30
list = ClearDoubleLinkedList(list);
printList(list); // (空)
list = ClearDoubleLinkedList(list); // 空表調用
return 0;
}
雙向鏈表清空利用 prior 指針實現了「邊遍歷邊釋放前驅」的優雅模式，代碼比單向鏈表更簡潔。**生產環境必須使用迭代法**，避免遞歸棧溢出。若使用帶頭結點循環雙向鏈表 (Linux list_head)，清空可簡化為 while (!list_empty(head)) { list_del(head->next); free(head->next); }，進一步體現標準庫接口的威力。
