數據結構（C語言篇）：（七）雙向鏈表

前言

????????數據結構作為計算機科學的核心基礎之一，其高效性與靈活性直接影響程序性能。雙向鏈表以其獨特的雙指針結構脫穎而出，既繼承了單鏈表的動態內存管理優勢，又通過前驅指針實現了逆向遍歷與快速節點刪除。這種結構在操作系統內核、數據庫索引及LRU緩存淘汰算法等場景中展現關鍵價值。本文將深入剖析雙向鏈表的實現原理、時間復雜度權衡及典型應用場景，下面就讓我們正式開始吧！

一、概念與結構

? ? ? ? 如上圖所示，帶頭鏈表里的頭結點，實際為“哨兵位”，哨兵位結點不存儲任何有效元素，只是站在這里“放哨”的。

? ? ? ? 需要注意的是，這里的“帶頭”和前面博客中提到的“頭結點”是兩個概念，實際前面的在單鏈表階段稱呼是不嚴謹的，但是為了更好地幫助大家理解，我們才直接稱為單鏈表的頭結點。

二、雙向鏈表的實現

2.1? 頭文件的準備

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next; //指針保存下?個結點的地址struct ListNode* prev; //指針保存前?個結點的地址LTDataType data;
}LTNode;//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插?數據
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode *LTFind(LTNode* phead,LTDataType x);

2.2? 函數的實現

2.2.1? LTPushBack( )函數（尾插）

? ? ? ? 我們先來畫圖分析一下：

? ? ? ? 當然，在正式實現尾插函數之前，我們照舊還得先寫一下雙向鏈表的創建結點函數、鏈表初始化函數和鏈表打印函數 —— LTBuyNode( )、LTInit( )和LTPrint( )，如下所示：

（1）LTBuyNode( )

? ? ? ? 實現邏輯如下：

內存分配：為新節點分配內存空間
內存檢查：檢查內存分配是否成功
數據賦值：將數據存儲到新節點
指針初始化：將前驅和后繼指針都指向自己（循環鏈表特性）

? ? ? ? 完整代碼如下：

LTNode* LTBuyNode(LTDataType x) {// 1. 內存分配LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));// 2. 內存分配失敗檢查if (newnode == NULL) {perror("malloc fail!");  // 打印錯誤信息exit(1);                 // 退出程序}// 3. 數據賦值newnode->data = x;// 4. 指針初始化（雙向循環鏈表的關鍵）newnode->next = newnode->prev = newnode;return newnode;
}

（2）LTInit( )

? ? ? ? 該函數的實現邏輯如下：

創建哨兵節點：使用LTBuyNode函數創建特殊節點
返回鏈表頭：返回指向哨兵節點的指針
建立空鏈表：初始化一個標準的空雙向循環鏈表

? ? ? ? 完整代碼如下：

// 初始化雙向循環鏈表
LTNode* LTInit() {// 1. 創建哨兵節點，通常使用特殊值（如-1）標記LTNode* phead = LTBuyNode(-1);// 2. 返回哨兵節點作為鏈表頭return phead;
}

（3）LTPrint( )

? ? ? ? 該函數的實現邏輯如下：

遍歷鏈表：從第一個有效節點開始遍歷
打印數據：輸出每個節點的數據值
循環檢測：利用哨兵節點作為循環終止條件
格式化輸出：使用箭頭表示節點間的連接關系

? ? ? ? 完整代碼如下：

void LTPrint(LTNode* phead) {// 1. 從第一個有效節點開始（跳過哨兵節點）LTNode* pcur = phead->next;// 2. 遍歷鏈表，直到回到哨兵節點while (pcur != phead) {printf("%d -> ", pcur->data);  // 打印當前節點數據pcur = pcur->next;            // 移動到下一個節點}// 3. 打印換行，結束輸出printf("\n");
}

（4）LTPushBack( )

? ? ? ? 該函數的實現邏輯如下：

參數驗證：確保頭結點phead不為NULL。
```
assert(phead);
```
創建新節點：使用LTBuyNode函數創建新結點，新結點包含數據x，prev和next指針初始化
```
LTNode* newnode = LTBuyNode(x);
```
設置新結點的指針：newnode->prev?指向原來的尾節點（即?phead->prev）；newnode->next?指向頭節點?phead。
```
newnode->prev = phead->prev;
newnode->next = phead;
```
更新相鄰結點的指針：將原來的尾結點的next指向新結點，將頭結點的prev指向新結點（現在的新結點稱為新的尾結點）。
```
phead->prev->next = newnode;
phead->prev = newnode;
```

? ? ? ? ????????完整代碼如下：

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

2.2.2? LTPushFront( )函數（頭插）

? ? ? ? 畫圖分析如下：

? ? ? ? 函數實現邏輯如下：

????????1.參數驗證：確保頭結點phead不為NULL。

????????2.創建新結點：調用LTBuyNode函數創建新結點。

????????3.設置新結點的指針：newnode->next?指向原來的第一個數據節點（即?phead->next）；newnode->prev?指向頭節點?phead。

newnode->next = phead->next;
newnode->prev = phead;

????????4.更新相鄰結點的指針：將原來的第一個數據節點的?prev?指向新節點；將頭節點的?next?指向新節點（現在新節點成為新的第一個數據節點）。

phead->next->prev = newnode;
phead->next = newnode;

? ? ? ? 完整代碼如下：

//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

2.2.3? LTPopBack( )函數（尾刪）

? ? ? ? 首先我們要先來實現一個判空函數LTEmpty（）：

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

? ? ? ? 下面來畫圖分析一下：

? ? ? ? 實現邏輯分析如下：

????????1.前置條件檢查：使用LTEmpty?函數檢查鏈表是否為空；如果鏈表為空（只有頭節點），則斷言失敗，不能刪除；確保鏈表至少有一個數據節點可刪除。

assert(!LTEmpty(phead));

? ? ? ??2.定位要刪除的結點：尾結點就是頭結點的?prev?指向的節點；將尾節點保存到?del?變量中。

LTNode* del = phead->prev;

????????3.更新指針連接：

del->prev->next = phead：將尾節點的前一個節點的?next?指向頭節點
phead->prev = del->prev：將頭節點的?prev?指向尾節點的前一個節點

del->prev->next = phead;
phead->prev = del->prev;

????????4.釋放內存：釋放被刪除結點的內存；將指針置為NULL，避免野指針。

free(del);
del = NULL;

? ? ? ? 完整代碼如下：

//尾刪
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

2.2.4? LTPopFront( )函數（頭刪）

? ? ? ? 畫圖分析如下：

? ? ? ? 函數實現邏輯如下：

????????1.前置條件檢查：使用?LTEmpty?函數檢查鏈表是否為空。

????????2.定位要刪除的結點：第一個數據節點就是頭結點的next指向的結點；將該結點保存到?del?變量中。

LTNode* del = phead->next;

????????3.更新指針連接：

del->next->prev = phead：將第二個數據節點的?prev?指向頭節點
phead->next = del->next：將頭節點的?next?指向第二個數據節點
這樣就跳過了要刪除的第一個數據節點
```
del->next->prev = phead;
phead->next = del->next;
```
4.釋放內存：釋放被刪除節點的內存；將指針置為?NULL，避免野指針。

? ? ? ? 完整代碼如下：

//頭刪
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

2.2.5? LTInsert( )函數（在pos位置之后插入數據）

? ? ? ? 畫圖分析如下：

? ? ? ? 實現邏輯：

????????1. 參數驗證：確保?pos?節點不為?NULL。

????????2.創建新結點：調用?LTBuyNode?函數創建新節點。

????????3.設置新結點的指針：

newnode->prev?指向?pos?節點（前驅節點）
newnode->next?指向?pos?節點原來的下一個節點
```
newnode->prev = pos;
newnode->next = pos->next;
```
4.更新相鄰結點的指針：
將?pos?節點原下一個節點的?prev?指向新節點
將?pos?節點的?next?指向新節點

pos->next->prev = newnode;
pos->next = newnode;

? ? ? ? 完整代碼如下：

//在pos位置之后插?數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

2.2.6? LTErase( )函數（刪除pos位置的結點）

? ? ? ? 先畫圖分析一下：

? ? ? ? 實現邏輯分析如下：

? ? ? ??1.參數驗證：確保?pos?節點不為?NULL。

? ? ? ? 2.更新指針連接（跳過要刪除的節點）：

pos->prev->next = pos->next：將前驅節點的?next?指向后繼節點
pos->next->prev = pos->prev：將后繼節點的?prev?指向前驅節點

這樣就完全跳過了要刪除的?pos?節點

pos->prev->next = pos->next;
pos->next->prev = pos->prev;

3.釋放內存：釋放被刪除節點的內存。

free(pos);
pos = NULL;

完整代碼如下所示：

//刪除pos位置的節點
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.2.7? LTFind( )函數（查找結點）

? ? ? ? 實現邏輯如下：

????????1.參數驗證：確保頭節點?phead?不為?NULL

????????2.初始化遍歷指針：創建當前指針?pcur?并初始化為第一個數據節點（phead->next）；跳過哨兵頭節點，從第一個數據節點開始遍歷。

LTNode* pcur = phead->next;

????????3.遍歷鏈表查找數據：循環條件?pcur != phead：當回到頭節點時停止（完成一圈遍歷）；對每個數據節點檢查其?data?是否等于目標值?x；如果找到匹配的節點，立即返回該節點的指針。

while (pcur != phead)
{if (pcur->data == x){return pcur;}pcur = pcur->next;
}

????????4.未找到的情況：如果遍歷完所有數據節點都沒有找到匹配的節點；返回?NULL?表示查找失敗。

return NULL;

? ? ? ? 完整代碼如下：

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//未找到return NULL;
}

2.2.8? LTDestroy( )函數（銷毀）

? ? ? ? 畫圖分析如下：

? ? ? ? 函數實現邏輯：

????????1.初始化遍歷指針：創建當前指針?pcur?并初始化為第一個數據節點；從頭節點的下一個節點開始遍歷。

LTNode* pcur = phead->next;

????????2.遍歷并釋放所有數據結點：

循環條件：pcur != phead?—— 當回到頭節點時停止；
保存下一個節點：在釋放當前節點前，先保存下一個節點的指針；
釋放當前節點：使用?free()?釋放當前數據節點的內存；
移動到下一個節點：將?pcur?指向之前保存的下一個節點。

while (pcur != phead)
{LTNode* next = pcur->next;free(pcur);pcur = next;
}

????????3.釋放頭結點：釋放頭節點（哨兵節點）的內存；將指針置為?NULL，避免野指針。

free(phead);
phead = NULL;

? ? ? ? 完整代碼如下：

//銷毀
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//銷毀頭結點free(phead);phead = NULL;
}

三、順序表與鏈表的分析

不同點	順序表	鏈表（單鏈表）
存儲空間上	物理上?定連續	邏輯上連續，但物理上不?定連續
隨機訪問	?持O(1)	不?持：O(N)
任意位置插?或者刪除元素	可能需要搬移元素，效率低O(N)	只需修改指針指向
插?	動態順序表，空間不夠時需要擴容和空間浪費	沒有容量的概念，按需申請釋放，不存在空間浪費
應?場景	元素?效存儲+頻繁訪問	任意位置?效插?和刪除