目錄
一、簡介
二. 雙鏈表的實現(xiàn)
1.準備工作及其注意事項
1.1 先創(chuàng)建三個文件
1.2 注意事項：幫助高效記憶
1.3? ?關(guān)于什么時候 用 一級指針接收，什么時候用 二級指針接收？
1.4 釋放節(jié)點時，要將節(jié)點地址 置為NULL，難道 節(jié)點內(nèi)部的 指針域的指針 就不用置為 NULL嗎？?
2.雙鏈表的基本功能接口
2.1?初始化哨兵位
?2.2 鏈表的創(chuàng)建新節(jié)點接口
2.3?打印
3. 插入 接口
3.1 尾插法
3.2 頭插法
3.3?在 pos 位置之后插入數(shù)據(jù)
4. 查找
5.刪除? 接口
5.1 尾刪法
5.2?頭刪法
5.3??刪除 pos 位置的數(shù)據(jù)
6. 銷毀鏈表 接口
6.1?二級指針版?
6.2?一級指針版
7. 總代碼概覽
List.h
List.c
test.c
三. 順序表和雙向鏈表的優(yōu)缺點分析
一、簡介
? ? ? ? 單向鏈表在解決那些需要大量查找前趨節(jié)點的問題時，效率較為低下，因為單向鏈表適合“從前往后”查找，并不適合“從后往前”查找。
（若想要看 單鏈表，可以點擊跳轉(zhuǎn)：【數(shù)據(jù)結(jié)構(gòu)】單向鏈表實現(xiàn) 超詳細）
如果要提高鏈表的查找效率，那??雙向鏈表（雙鏈表）無疑是首選。
雙向鏈表：即為 字面上的意思是“雙向”的鏈表，如下圖所示。
?
? ? ? ?
- 雙向 指各個節(jié)點之間的邏輯關(guān)系是 雙向的，該鏈表通常 有一個頭節(jié)點 -- 稱為 哨兵位 。
- 概念:?當鏈表中只有哨兵位節(jié)點的時候，我們稱該鏈表為空鏈表，即哨兵位是不能刪除的
- 從上圖還可以看出，雙向鏈表中每個節(jié)點包括一下3個部分，分別是：
- 指針域（前驅(qū)節(jié)點 prev ）、
- 數(shù)據(jù)域（用于存儲數(shù)據(jù)元素 data）
- 指針域（后繼節(jié)點 next)。
二. 雙鏈表的實現(xiàn)
1.準備工作及其注意事項
1.1 先創(chuàng)建三個文件
?
?解釋這三個文件的作用
?1、頭文件List.h ?是來聲明接口函數(shù)，定義鏈表，將幾個公共用到的庫函數(shù)集合起來
?2、源文件List.c ?是用來具體實現(xiàn)接口
?3、源文件test.c ?用于接口的測試工作 ，即具體的使用場景
1.2 注意事項：幫助高效記憶
1.?傳遞指針，都要斷言 不能為 NULL ，指針不能為空：assert(phead);
2. 存在?關(guān)系到? 前趨節(jié)點prev 或 后繼節(jié)點next? 的 情況，? ? 可以 直接定義變量 Prev = .... Next = ....? ?便于 理清思路，不易亂
3. 所有的 刪除接口 都需要 斷言鏈表不能只有 哨兵位： assert(phead->next != phead);?
4. 尾刪法: 記得雙鏈表的找尾 不像 單鏈表需要循環(huán)去找尾??！ptail = phead->prev;5. 初始化創(chuàng)建頭節(jié)點：推薦使用 調(diào)用 創(chuàng)建節(jié)點接口? 的 方法
5. 銷毀接口：推薦使用 傳一級指針的方法
1.3? ?關(guān)于什么時候 用 一級指針接收，什么時候用 二級指針接收？（不看水話，可以直接 看下面?總結(jié) 部分）
（有點水話，實在不明白思路的可以看一下詳細解說的 ”水話“）
? ? ? ? ?在 單向鏈表 中，有一個指向 第一個節(jié)點的指針 plist，由于 頭插法等操作，可能會改變 第一個節(jié)點，則 plist 要對應進行 更新，而 要想直接改變一個變量（plist是指針變量）的值，需要傳地址，plist 的 &plist 是 一級指針的地址，就要用 二級指針 來接收
? ? ? ? ?在 雙向鏈表 中，存在 頭節(jié)點 head ，即 哨兵位，哨兵是 不用進行 改變本身這個節(jié)點的 地址的??！
那就有鐵鐵要問了，不是還要改變?頭節(jié)點 head（?哨兵位 ） 的指向，要指向 第一個 節(jié)點 或 尾節(jié)點 嗎？?
回答：因為 我們 要改變的 是 雙鏈表節(jié)點 結(jié)構(gòu)?中 的 結(jié)構(gòu)體成員變量：prev 和 next ，改變 結(jié)構(gòu)體的成員變量?只需要利用 結(jié)構(gòu)體指針 p->prev = .... 或 p->next? ?= .... 就達到 修改 雙鏈表節(jié)點指向 問題了，而你本身并不需要改變 一個節(jié)點的地址 p
總結(jié)?
總結(jié)：修改?雙鏈表節(jié)點 的指向，是通過? 修改節(jié)點結(jié)構(gòu)體內(nèi)部的 兩個成員變量 來實現(xiàn)的，只需要用到 結(jié)構(gòu)體指針（即該節(jié)點的地址 p），找到? 兩個成員變量，即可完成修改，因而傳遞 一級指針就好，不用像 單鏈表那樣還要 傳遞 一級指針的 地址
1.4 釋放節(jié)點時，要將節(jié)點地址 置為NULL，難道 節(jié)點內(nèi)部的 指針域的指針 就不用置為 NULL嗎？?
回答：不用 因為節(jié)點的空間已經(jīng)還給操作系統(tǒng)了 那個指針域的指針所占據(jù)的空間也還回去了 操作系統(tǒng)后續(xù)分配內(nèi)存就會把那塊空間覆蓋掉 就不會又啥影響
2.雙鏈表的基本功能接口
2.1?初始化哨兵位
初始化哨兵位 第一種方法：傳入 指針，進行"加工" 成 哨兵位
// 初始化一個哨兵位：
void LTInit(LTNode** pphead)
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
// 開辟空間是否成功的判斷：一般malloc不會失敗，失敗證明內(nèi)存不夠了，寫下面的證明算是好習慣，不寫一般沒問題
if (*pphead == NULL) {
perror("malloc fail!");
exit(1);
}
(*pphead)->data = -1;
(*pphead)->next = (*pphead)->prev = *pphead; // 哨兵位初識化，兩個指針都指向自己
}初始化哨兵位第二種方法：直接一個函數(shù)生成一個哨兵位，返回哨兵位就好，不用傳指針
LTNode* LTInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
// 開辟空間是否成功的判斷
if (phead == NULL) {
perror("malloc fail!");
exit(1);
}
phead->data = -1; // data 隨便定，反正哨兵位data無效
phead->next = phead->prev = phead;
return phead;
}
初始化哨兵位 第二種方法的2.0 版本：因為哨兵位的初始化 和 2.2 創(chuàng)建新新節(jié)點的方法一樣，可以合并調(diào)用
LTNode* LTInit_2()
{
LTNode* phead = LTCreatNode(-1);
return phead;
}?2.2 鏈表的創(chuàng)建新節(jié)點接口
// 創(chuàng)建新節(jié)點
LTNode* LTCreatNode(LTDataType x)
{
LTNode* newNode = (LTNode*)malloc(sizeof (LTNode));
if (newNode == NULL)
{
perror("malloc fail!");
exit(1);
}
newNode->data = x;
newNode->prev = newNode->next = newNode; // 都是 指向自己
return newNode;
}
2.3?打印
雙鏈表的打印
和 單鏈表打印一樣，都需要循環(huán)，但是結(jié)束條件不一樣
單鏈表以 pcur = NULL 為結(jié)束條件，雙鏈表是 一種循環(huán)鏈表，頭尾相連，不會有 ?pcur = NULL 的情況
正解：既然 哨兵位無有效數(shù)據(jù)，同時 循環(huán)一輪 還是 回到頭（哨兵位），干脆：while (pcur != phead)
void LTPrint(LTNode* phead)
{
assert(phead);// 哨兵位不能為空
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("\n");
}3. 插入 接口
前言：
// 不需要改變哨兵位，則不需要傳二級指針
// 如果需要修改哨兵位的話，則傳二級指針
3.1 尾插法
?
?
雙鏈表的 尾插法
雙向鏈表尾插需不需要找尾的操作 ?不需要 ：ptail = head->prev; ?注意這個 等價關(guān)系，便于理解下面的代碼
尾插法 也稱作 在哨兵位之前插入節(jié)點/最后一個有效節(jié)點之后插入數(shù)據(jù)
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);// 哨兵位不能為空
LTNode* newNode = LTCreatNode(x);
LTNode* ptail = phead->prev;
// 三者關(guān)系：phead->prev(即ptail) newNode phead
// 處理順序：先 newNode， 再 phead->prev(即ptail) ，最后 phead：否則會亂套
// 先 newNode
newNode->next = phead;
newNode->prev = ptail; // 就是 phead->prev
// 再尾節(jié)點 ptail = head->prev ; ptail -> next = head-> prev -> next;
ptail->next = newNode;
// 最后頭節(jié)點
phead->prev = newNode;
}
3.2 頭插法
雙鏈表的 頭插法
注意：頭插 是在第一個有效位置進行插入，不是在哨兵位 前面，由于 雙鏈表的循環(huán)成環(huán)狀的特性，若在哨兵位前面，就是尾插了
?
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newNode = LTCreatNode(x);
// 三者關(guān)系：phead newNode phead->next (即 第一個 有效節(jié)點，命名為Next) ;
// 處理順序：先 newNode， 再 phead->next(即 第一個 有效節(jié)點，命名為Next) ，最后 phead：否則會亂套
LTNode* Next = phead->next; // 這里就是定義了個變量，便于梳理
// 先 newNode
newNode->next = Next;
newNode->prev = phead;
// 再 phead->next(即 第一個 有效節(jié)點)
Next->prev = newNode;
// 最后頭節(jié)點
phead->next = newNode;
}3.3?在 pos 位置之后插入數(shù)據(jù)
在 pos 位置之后插入數(shù)據(jù)：要配合? ?4.查找? ?接口實現(xiàn)
和 頭插法思路一樣：只是將 哨兵的帶頭作用 換成了 pos
pos 是通過 4.查找 的接口找的
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
// 先創(chuàng)建新節(jié)點
LTNode* newNode = LTCreatNode(x);
// 關(guān)系三個節(jié)點：pos newNode pos->next
// 先處理newNode，后 pos->next ， 最后 pos
// 注意三者的執(zhí)行順序 不能換！！
LTNode* Next = pos->next; // 這里將 pos 的下一個節(jié)點(pos->next) 命名成 Next （避免和 next 混淆）
newNode->next = Next;
newNode->prev = pos;
Next->prev = newNode;
pos->next = newNode;
}4. 查找
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;
}5.刪除? 接口
5.1 尾刪法
// 思路：讓 倒數(shù)第二個 節(jié)點 next 指向 head ，head 指向 倒數(shù)第二個節(jié)點，最后 free 掉 ptail
// 尾節(jié)點前一個節(jié)點：ptail->prev = phead->prev->prev
// 尾節(jié)點：ptail = phead->prev
// "尾節(jié)點前一個節(jié)點" 指向 head哨兵位：ptail->prev->next = phead;
// head哨兵位 指向 "尾節(jié)點前一個節(jié)點" ：phead->prev = ptail->prev;
// 最后 free 掉 ptail
?
// 尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);
//鏈表為空：只有一個哨兵位節(jié)點
assert(phead->next != phead);
LTNode* ptail = phead->prev;
ptail->prev->next = phead;
phead->prev = ptail->prev;
free(ptail);
ptail = NULL;
}
5.2?頭刪法
? ? //? 被刪除的 第一個有效節(jié)點：pFirst = phead->next;?
? ? // ?下一個節(jié)點 pSecond = pFirst->next;
?? ?//? 先 下一個節(jié)點 指向 head ： pSecond->prev = phead;
?? ?//? 后 head 指向 下一個節(jié)點 ：phead->next = pSecond;?
?? ?//? 注意：因為對于循環(huán)鏈表來說， 第一個節(jié)點的下個節(jié)點 也可以是 哨兵位，所以 只存在一個有效節(jié)點，也是可以直接刪除第一個節(jié)點的、
// 頭刪
// 刪除的是 第一個有效節(jié)點
void LTPopFront(LTNode* phead)
{
assert(phead); // 地址不能為NULL
assert(phead->next != phead); // 鏈表不能只有 哨兵位
LTNode* pFirst = phead->next; // 要被刪除的 第一個節(jié)點
LTNode* pSecond = pFirst->next;
pSecond->prev = phead;
phead->next = pSecond;
free(pFirst);
pFirst = NULL;
}5.3??刪除 pos 位置的數(shù)據(jù)
刪除 pos 位置的數(shù)據(jù)：要配合? ?4.查找? ?接口實現(xiàn)
void LTErase(LTNode* pos)
{
?? ?assert(pos);
?? ?// 關(guān)系三個節(jié)點： pos->prev ? ? ?pos ? ? pos->next ? ??
?? ?LTNode* Prev = pos->prev; // ?pos 的前一個?
?? ?LTNode* Next = pos->next; // ?pos 的下一個
?? ?Next->prev = Prev;
?? ?Prev->next = Next;
?? ?free(pos);
?? ?pos = NULL;
}6. 銷毀鏈表 接口
更推薦 一級指針版：手動置為NULL
為了保持 接口的一致性：不然前面接口都是 一級指針，到這里突然 二級指針，當程序交給用戶時，會增加記憶的成本
6.1?二級指針版?
// 思路：先將 有效節(jié)點刪除，后刪除哨兵位
// 刪除有效節(jié)點, 要將下個節(jié)點保存起來，不然找不到
// 注意：這里 最后需要 ? 改變 ?哨兵位 為NULL ，因而要傳遞地址，用二級指針接收
// 否則，傳值 只會影響 形參，哨兵位 需要手動 置為NULL
void LTDestory(LTNode** pphead)
{
assert(pphead);// 指針本身不能為 空
assert(*pphead); // 哨兵位 不能為 空
LTNode* pcur = (*pphead)->next; // *pphead = phead 即哨兵位 ;還有記得 加括號
while (pcur != *pphead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
// 最后刪除 哨兵位
free(*pphead);
*pphead = NULL;
}
6.2?一級指針版
// 雙鏈表的 銷毀：一級指針版：哨兵位 需要 手動額外 置為空
void LTDestory(LTNode* phead)
{
?? ?assert(phead);// 哨兵位 不能為 空
?? ?LTNode* pcur = (phead)->next; // *pphead = phead 即哨兵位 ;還有記得 加括號
?? ?while (pcur != phead)
?? ?{
?? ??? ?LTNode* next = pcur->next;
?? ??? ?free(pcur);
?? ??? ?pcur = next;
?? ?}
?? ?// 最后釋放掉 形參的指針：這里不是釋放 哨兵位
?? ?free(phead);
?? ?phead = NULL;
}
7. 總代碼概覽
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 創(chuàng)建新節(jié)點
typedef int LTDataType;
typedef struct LTistNode
{
LTDataType data;
struct LTistNode* prev;
struct LTistNode* next;
}LTNode;
// 創(chuàng)建新節(jié)點
LTNode* LTCreatNode(LTDataType x);
// 初始化：生成哨兵位
LTNode* LTInit();
// 打印函數(shù)
void LTPrint(LTNode* phead);
// 尾插法
void LTPushBack(LTNode* phead, LTDataType x);
// 頭插法
void LTPushFront(LTNode* phead, LTDataType x);
// 在 pos 之后插入數(shù)據(jù)
void LTInsert(LTNode* pos, LTDataType x);
// 尾刪法
void LTPopBack(LTNode* phead);
// 頭刪法
void LTPopFront(LTNode* phead);
// 刪除 pos 位置節(jié)點
void LTErase(LTNode* pos);
// 查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 銷毀
void LTDestory(LTNode* phead);List.c
#include"List.h"
// 創(chuàng)建新節(jié)點
LTNode* LTCreatNode(LTDataType x)
{
LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
if (newNode == NULL)
{
perror("malloc fail!");
exit(1);
}
newNode->data = x;
newNode->prev = newNode->next = newNode;
return newNode;
}
// 初始化：生成哨兵位
LTNode* LTInit()
{
LTNode* head = LTCreatNode(-1);
return head;
}
// 打印函數(shù)
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
// 尾插法
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
// 創(chuàng)建新節(jié)點
LTNode* newNode = LTCreatNode(x);
LTNode* ptail = phead->prev;
// 三者關(guān)系：ptail newNode phead
newNode->next = phead;
newNode->prev = ptail;
ptail->next = newNode;
phead->prev = newNode;
}
// 頭插法
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
// 創(chuàng)建新節(jié)點
LTNode* newNode = LTCreatNode(x);
// 三者關(guān)系：phead newNode phead->next (定為Next);
LTNode* Next = phead->next; // 這里就是定義了個變量，便于梳理
newNode->next = Next;
newNode->prev = phead;
Next->prev = newNode;
phead->next = newNode;
}
// 查找
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 之后插入數(shù)據(jù)：頭插法實現(xiàn)邏輯一樣
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
// 創(chuàng)建新節(jié)點
LTNode* newNode = LTCreatNode(x);
// 三者關(guān)系：pos newNode pso->next (定為Next);
LTNode* Next = pos->next;
newNode->next = Next;
newNode->prev = pos;
Next->prev = newNode;
pos->next = newNode;
}
// 尾刪法:記得雙鏈表的找尾 不像 單鏈表需要循環(huán)去找尾
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);// 鏈表不能只有 哨兵位 （刪除的接口 都要斷言這條）
// 三者關(guān)系：ptail->prev ptail head
LTNode* ptail = phead->prev;
ptail->prev->next = phead;
phead->prev = ptail->prev;
free(ptail);
ptail = NULL;
}
// 頭刪法
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead); // 鏈表不能只有 哨兵位 （刪除的接口 都要斷言這條）
// 三者關(guān)系：phead phead->next phead->next->next(命名為pSecond)
LTNode* pFirst = phead->next; // 要被刪除的 第一個節(jié)點 一定要先保存下來！！
LTNode* pSecond = pFirst->next;
pSecond->prev = phead;
phead->next = pSecond;
free(pFirst);
pFirst = NULL;
}
// 刪除 pos 位置節(jié)點
void LTErase(LTNode* pos)
{
assert(pos);
// 關(guān)系三個節(jié)點：pos->prev pos pos->next
LTNode* Prev = pos->prev; // pos 的前一個
LTNode* Next = pos->next; // pos 的下一個
Next->prev = Prev;
Prev->next = Next;
free(pos);
pos = NULL;
}
// 銷毀
void LTDestory(LTNode* phead)
{
assert(phead);
// 先全部刪除有效節(jié)點，后刪除頭節(jié)點
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 LTTest()
{
// 創(chuàng)建哨兵位
LTNode* head = LTInit(); // 這里直接用 head 代表哨兵位：更直觀一點，和 前面講解用的 plist 是一樣的
// 尾插法
LTPushBack(head, 1);
LTPushBack(head, 2);
LTPushBack(head, 3);
LTPushBack(head, 4); // 1 -> 2 -> 3 -> 4 ->
printf("測試尾插：");
LTPrint(head);
// 頭插法
LTPushFront(head, 5);
LTPushFront(head, 6);// 6 -> 5 -> 1 -> 2 -> 3 -> 4 ->
printf("測試頭插：");
LTPrint(head);
// 查找
//LTFind(head, 1);
// 在 pos 之后插入數(shù)據(jù)：頭插法實現(xiàn)邏輯一樣
LTNode* FindRet1 = LTFind(head, 1);
LTInsert(FindRet1, 100);
LTNode* FindRet2 = LTFind(head, 2);
LTInsert(FindRet2, 200); // 6 -> 5 -> 1 -> 100 -> 2 -> 200 -> 3 -> 4 ->
printf("測試pos 之后插入：");
LTPrint(head);
// 頭刪法
LTPopFront(head);
LTPopFront(head); // 1 -> 100 -> 2 -> 200 -> 3 -> 4 ->
printf("測試頭刪：");
LTPrint(head);
// 尾刪法:記得雙鏈表的找尾 不像 單鏈表需要循環(huán)去找尾
LTPopBack(head);
LTPopBack(head); // 1 -> 100 -> 2 -> 200 ->
printf("測試尾刪：");
LTPrint(head);
// 刪除 pos 位置節(jié)點
LTNode* FindRet3 = LTFind(head, 1);
LTErase(FindRet3); // 100 -> 2 -> 200 ->
printf("測試刪除 pos 位置節(jié)點：");
LTPrint(head);
// 雙鏈表的 銷毀：這里就不演示銷毀了
//LTDesTroy(head);
//head= NULL; //哨兵位 需要手動 置為NULL
}
int main()
{
LTTest();
return 0;
}三. 順序表和雙向鏈表的優(yōu)缺點分析
| 不同點 |
順序表 |
鏈表（單鏈表） |
| 存儲空間上 |
物理上?定連續(xù) |
邏輯上連續(xù)，但物理上不?定連續(xù) |
| 隨機訪問 |
支持O(1) |
不支持：O(N) |
| 任意位置插?或者刪除元素 |
可能需要搬移元素，效率低O(N) |
只需修改指針指向 |
| 插入 |
動態(tài)順序表，空間不夠時需要擴容 |
沒有容量的概念 |
| 應用場景 |
元素高效存儲+頻繁訪問 |
任意位置插?和刪除頻繁 |
完。文章來源：http://www.zghlxwxcb.cn/news/detail-829173.html
若上述文章有什么錯誤，歡迎各位大佬及時指出，我們共同進步！文章來源地址http://www.zghlxwxcb.cn/news/detail-829173.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表 超詳細 （含：何時用一級指針或二級指針；指針域的指針是否要釋放）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
