引言
場景描述
想象一個 環形地鐵線路(如深圳地鐵11號線),這條線路首尾相連,列車可以順時針或逆時針循環行駛。為了方便管理,地鐵系統設置了一個 “虛擬調度中心”(頭節點),它不承載乘客,但作為整個環線的邏輯起點和終點,用于監控和協調所有站點的運行。
映射關系
雙向循環鏈表結構 | 地鐵環線系統 |
---|---|
頭節點(不存儲數據) | 虛擬調度中心(無乘客上下車) |
數據節點 | 地鐵站點(如“沙井站”、“馬安山站”) |
next 指針 | 順時針方向的下一個站點 |
prev 指針 | 逆時針方向的上一個站點 |
循環結構 | 線路首尾相連,列車可雙向循環行駛 |
一、數據結構定義
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
} LTNode;
- 節點結構:
data
:存儲節點數據next
:指向下一個節點prev
:指向前一個節點
- 循環特性:
- 頭節點的
next
指向第一個有效節點 - 頭節點的
prev
指向最后一個節點 - 形成閉環結構(頭節點自環表示空鏈表)
- 頭節點的
二、核心函數實現詳解
1. 節點創建函數 LTBuyNode
LTNode* LTBuyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode; // 初始自環return newnode;
}
-
功能:動態分配內存創建新節點。
-
細節:
-
數據域初始化為
x
。 -
next
和prev
指針初始指向自身,形成自環結構。 -
若內存分配失敗,程序直接終止(
exit(1)
)。
-
2. 鏈表初始化 LTInit
LTNode* LTInit() {LTNode* phead = LTBuyNode(-1); // 頭節點數據為-1return phead;
}
-
功能:創建帶頭節點的空鏈表。
-
細節:
-
頭節點數據為
-1
,next
和prev
均指向自身。 -
空鏈表僅含頭節點,邏輯上表示鏈表為空。
-
3. 打印鏈表 LTPrint
void LTPrint(LTNode* phead) {LTNode* pcur = phead->next;while (pcur != phead) {printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}
-
功能:遍歷鏈表并打印所有數據節點(不打印頭節點)。
-
細節:
-
從頭節點的下一個節點開始遍歷,直到回到頭節點結束。
-
輸出格式為
1 -> 2 -> 3 -> ...
,末尾換行。
-
4. 尾插法 LTPushBack
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev; // 新節點prev指向原尾節點newnode->next = phead; // 新節點next指向頭節點phead->prev->next = newnode; // 原尾節點的next指向新節點phead->prev = newnode; // 頭節點的prev指向新節點
}
-
功能:在鏈表尾部插入新節點。
-
指針調整步驟:
-
新節點的
prev
指向原尾節點。 -
新節點的
next
指向頭節點。 -
原尾節點的
next
指向新節點。 -
頭節點的
prev
指向新節點。
-
5. 頭插法 LTPushFront
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next; // 新節點next指向原首節點newnode->prev = phead; // 新節點prev指向頭節點phead->next->prev = newnode; // 原首節點的prev指向新節點phead->next = newnode; // 頭節點的next指向新節點
}
-
功能:在鏈表頭部插入新節點。
-
指針調整步驟:
-
新節點的
next
指向原首節點。 -
新節點的
prev
指向頭節點。 -
原首節點的
prev
指向新節點。 -
頭節點的
next
指向新節點。
-
6. 鏈表判空 LTEmpty
bool LTEmpty(LTNode* phead) {assert(phead);return phead->next == phead; // 僅頭節點自環時為空
}
-
功能:判斷鏈表是否為空。
-
返回值:
-
true
:鏈表為空(僅頭節點存在)。 -
false
:鏈表至少有一個數據節點。
-
7. 尾刪法 LTPopBack
void LTPopBack(LTNode* phead) {assert(!LTEmpty(phead)); // 鏈表非空才能刪除LTNode* del = phead->prev; // 待刪除的尾節點del->prev->next = phead; // 尾節點前驅的next指向頭節點phead->prev = del->prev; // 頭節點的prev指向尾節點前驅free(del);del = NULL; // 局部指針置空(不影響外部)
}
-
功能:刪除鏈表尾節點。
-
細節:
-
斷言確保鏈表非空。
-
調整尾節點前驅的指針,跳過尾節點。
-
釋放尾節點內存,局部指針
del
置空。
-
8. 頭刪法 LTPopFront
void LTPopFront(LTNode* phead) {assert(!LTEmpty(phead));LTNode* del = phead->next; // 待刪除的首節點del->next->prev = phead; // 首節點后繼的prev指向頭節點phead->next = del->next; // 頭節點的next指向首節點后繼free(del);del = NULL;
}
-
功能:刪除鏈表首節點。
-
操作步驟:類似尾刪法,調整指針后釋放內存。
9. 查找節點 LTFind
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; // 未找到返回NULL
}
-
功能:查找第一個值為
x
的節點。 -
返回值:找到返回節點指針,否則返回
NULL
。
10. 在指定位置后插入 LTInsert
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next; // 新節點next指向pos的后繼newnode->prev = pos; // 新節點prev指向pospos->next->prev = newnode; // pos后繼的prev指向新節點pos->next = newnode; // pos的next指向新節點
}
-
功能:在
pos
節點后插入新節點。 -
應用場景:結合
LTFind
實現任意位置插入。
11. 在指定位置前插入 LTInsertFront
void LTInsertFront(LTNode* pos, LTDataType x) { assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos; // 新節點next指向posnewnode->prev = pos->prev; // 新節點prev指向pos的前驅pos->prev->next = newnode; // pos前驅的next指向新節點pos->prev = newnode; // pos的prev指向新節點
}
-
功能:在
pos
節點前插入新節點。
12. 刪除指定節點 LTErase
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next; // pos前驅的next指向pos的后繼pos->next->prev = pos->prev; // pos后繼的prev指向pos的前驅free(pos);pos = NULL; // 局部指針置空(外部指針需手動置空)
}
-
功能:刪除
pos
節點。 -
注意事項:
-
pos
不能是頭節點,否則鏈表結構被破壞。 -
調用后,外部指向
pos
的指針變為野指針,需手動置空。
-
13. 銷毀鏈表 LTDesTroy
void LTDesTroy(LTNode** phead) {LTNode* pcur = (*phead)->next;while (pcur != *phead) { // 遍歷釋放所有數據節點LTNode* next = pcur->next;free(pcur);pcur = next;}free(*phead); // 釋放頭節點*phead = NULL; // 頭指針置空
}
-
功能:銷毀整個鏈表,釋放所有內存。
-
設計:
-
使用二級指針確保外部頭指針被置空。
-
避免內存泄漏和野指針問題。
-
測試用例解析 test01
void test01() {LTNode* plist = LTInit(); // 初始化空鏈表LTPushBack(plist, 1); // 尾插1LTPushBack(plist, 2); // 尾插2 → 鏈表: 1 -> 2LTPushBack(plist, 3); // 尾插3 → 鏈表: 1 -> 2 -> 3LTPushBack(plist, 4); // 尾插4 → 鏈表: 1 -> 2 -> 3 -> 4LTPrint(plist); // 輸出: 1 -> 2 -> 3 -> 4LTPushFront(plist, 0); // 頭插0 → 鏈表: 0 -> 1 -> 2 -> 3 -> 4LTPrint(plist);LTPopBack(plist); // 尾刪4 → 鏈表: 0 -> 1 -> 2 -> 3LTPrint(plist);LTPopFront(plist); // 頭刪0 → 鏈表: 1 -> 2 -> 3LTPrint(plist);LTNode* pos = LTFind(plist, 2); // 查找值為2的節點if (pos) {LTInsert(pos, 5); // 在2后插入5 → 鏈表: 1 -> 2 -> 5 -> 3LTPrint(plist);}LTDesTroy(&plist); // 銷毀鏈表,plist置NULL
}
-
驗證操作:
-
初始化、尾插、頭插、尾刪、頭刪、查找、指定位置插入、銷毀。
-
通過打印驗證每一步操作的正確性
-
四、關鍵技術點總結
技術點 | 說明 |
---|---|
頭節點設計 | 簡化邊界條件處理,統一頭插尾插操作 |
循環鏈表特性 | 通過頭節點的 prev 指針快速訪問尾節點 |
指針操作技巧 | 插入需修改 4 個指針,刪除需修改 2 個指針 |
內存管理 | 使用LTBuyNode 統一分配內存,LTDesTroy 徹底釋放內存 |
安全性設計 | assert 參數校驗,內存釋放后置 NULL |
五、典型應用場景
- LRU 緩存:
- 通過頭尾指針快速訪問最近使用和最久未使用的節點
- 雙端隊列:
- 支持 O (1) 時間復雜度的頭尾操作
- 文件系統 inode 管理:
- 快速定位文件的前后節點
- 哈希表沖突處理:
- 雙向鏈表便于刪除操作
六、擴展學習建議
- 實現鏈表逆序操作
- 嘗試合并兩個有序鏈表
- 研究跳表(Skip List)數據結構
- 了解 Linux 內核中的鏈表實現
最后附上全部代碼:
代碼List.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//雙向鏈表的結構
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//打印鏈表
void LTPrint(LTNode* phead);//雙向鏈表但初始化
LTNode* LTInit();//銷毀數據表
void LTDesTroy(LTNode** phead);
//void LTDataTroy(LTNode* phead); //也可也傳一級指針不過,最后得自己NULL一下,// 尾插
void LTPushBack(LTNode* phead, LTDataType x);// 頭插
void LTPushFront(LTNode* phead, LTDataType x);//只有一個頭結點的情況下,雙向鏈表為空
bool LTEmpty(LTNode* phead);//尾刪
void LTPopBack(LTNode* phead);
//頭刪
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x);//在pos位置之前插入數據
void LTInsertFront(LTNode* pos, LTDataType x);//刪除pos位置的結點
void LTErase(LTNode* pos);
代碼List.c
#include"List.h"//創建新的結點
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//判斷新結點是否創建成功if (newnode == NULL){perror("malloc fail!");exit(1);}//成功就把值賦上和指針指向newnode->data = x;newnode->next = newnode->prev = newnode;//返回一級指針指向的地址return newnode;
}void LTPrint(LTNode* phead)
{//把頭結點的下一個指向的地址賦給新創建的臨時指針LTNode* pcur = phead->next;//遍歷鏈表的數據,遍歷到頭結點結束while (pcur != phead){printf("%d -> ", pcur->data);//把pcur下一個地址賦給自己pcur = pcur->next;}printf("\n");
}LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{//斷言phead不為空assert(phead);//創建新的結點LTNode* newnode = LTBuyNode(x);//把新的結點prev指向頭結點的prevnewnode->prev = phead->prev;//把新的next指向phead的地址newnode->next = phead;//把頭結點的prev的結點的next結點指向新的結點phead->prev->next = newnode;//把頭結點prev指向新的結點phead->prev = newnode;
}//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//只有一個頭結點的情況下,雙向鏈表為空
bool LTEmpty(LTNode* phead)
{assert(phead);//判斷 phead->next 是否等于 phead 來確定鏈表是否為空,若相等則返回 true,表示鏈表為空;否則返回 false。return phead->next == phead;
}//尾刪
void LTPopBack(LTNode* phead)
{//對LTEmpty函數取反assert(!(LTEmpty(phead)));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//頭刪
void LTPopFront(LTNode* phead)
{//對LTEmpty函數取反assert(!(LTEmpty(phead)));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = 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;
}
//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}
//在pos位置之前插入數據
void LTInsertFront(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;}//刪除pos位置的結點
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//銷毀數據表
void LTDesTroy(LTNode** phead)
{LTNode* pcur = (*phead)->next;while (pcur != *phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(*phead);*phead = NULL;
}//void LTDataTroy(LTNode* phead)
//{
// LTNode* pcur = phead->next;
// while (pcur != phead)
// {
// LTNode* next = pcur->next;
// free(pcur);
// pcur = next;
// }
// free(phead);
// phead = NULL;
//
//}
代碼test.c
#include"List.h"void test01()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPushFront(plist, 0);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* pos = LTFind(plist, 2);if (pos){LTInsert(pos, 5);LTPrint(plist);}LTDesTroy(&plist);
}int main()
{test01();return 0;
}