網(wǎng)站首頁 編程語言 正文
與單鏈表的區(qū)別
單向/雙向
單向：只有一個ｎｅｘｔ指針，只指向下一位元素
雙向：有兩個指針，指向上一位和下一位元素，尋找前一節(jié)點和后一節(jié)點很便利
帶頭/不帶頭
帶頭：在本來的頭結(jié)點之前還有一個哨兵衛(wèi)節(jié)點作為頭節(jié)點，它的址域指針指向頭節(jié)點，值域不做使用
不帶頭：沒有哨兵衛(wèi)頭節(jié)點，在尾刪尾插等問題中要考慮頭結(jié)點的情況（局限）
循環(huán)/非循環(huán)
循環(huán)：頭結(jié)點會與尾節(jié)點相連
非循環(huán)：頭結(jié)點不與尾節(jié)點相連
代碼的實現(xiàn)
接口
// 創(chuàng)建鏈表（鏈表初始化） ListNode* ListCreate(); //創(chuàng)建節(jié)點 ListNode* BuyListNode(ListNode* pHead); // 雙向鏈表銷毀 void ListDestory(ListNode* pHead); // 雙向鏈表打印 void ListPrint(ListNode* pHead); // 雙向鏈表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 雙向鏈表尾刪 void ListPopBack(ListNode* pHead); // 雙向鏈表頭插 void ListPushFront(ListNode* pHead, LTDataType x); // 雙向鏈表頭刪 void ListPopFront(ListNode* pHead); // 雙向鏈表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 雙向鏈表在pos的前面進(jìn)行插入 void ListInsert(ListNode* pos, LTDataType x); // 雙向鏈表刪除pos位置的節(jié)點 void ListErase(ListNode* pos);
節(jié)點的構(gòu)造
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
初始化鏈表
// 創(chuàng)建鏈表（初始化）
ListNode* ListCreate()
{
//開辟哨兵衛(wèi)頭結(jié)點
ListNode* plist = (ListNode*)malloc(sizeof(ListNode));
if (plist == NULL)//失敗打印錯誤信息并結(jié)束進(jìn)程
{
perror("ListCreat fail:");
exit(-1);
}
plist->next = plist;
plist->prev = plist;
return plist;
}
開辟節(jié)點
//創(chuàng)建節(jié)點
ListNode* BuyListNode(LTDataType x)
{
//創(chuàng)建節(jié)點
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)//失敗打印錯誤信息并結(jié)束進(jìn)程
{
perror("creatnode fail:");
exit(-1);
}
newnode->data = x;
//初始化結(jié)點
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
銷毀鏈表
注：動態(tài)開辟的鏈表空間，在不使用后需要將之釋放，避免造成內(nèi)存泄漏
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
ListNode* cur = pHead;
pHead->prev->next = NULL;
while (cur!=NULL)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
return;
}
打印鏈表
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建尋址指針
ListNode* cur = pHead->next;
//循環(huán)遍歷鏈表
while (cur != pHead)
{
//打印數(shù)據(jù)
printf("%d->", cur->data);
//找到下一個節(jié)點
cur = cur->next;
}printf("NULL\n");
return;
}
尾插鏈表
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建節(jié)點
ListNode* newnode = BuyListNode(x);
//找到尾節(jié)點
ListNode* tail=pHead->prev;
tail->next = newnode;
newnode->prev = tail;
pHead->prev = newnode;
newnode->next = pHead;
}
尾刪鏈表
尾刪前記錄前一節(jié)點的地址
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
//只剩哨兵衛(wèi)頭結(jié)點的情況
if (pHead->prev == pHead)
return;
//記錄尾節(jié)點及其前一節(jié)點
ListNode* tail = pHead->prev;
ListNode* tailprev = tail->prev;
//釋放尾節(jié)點
free(tail);
//構(gòu)建尾節(jié)點前一節(jié)點與哨兵衛(wèi)頭結(jié)點的關(guān)系
tailprev->next = pHead;
pHead->prev = tailprev;
return;
}
頭插鏈表
頭插前記錄哨兵衛(wèi)頭節(jié)點的下一節(jié)點
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建節(jié)點
ListNode* newnode = BuyListNode(x);
//記錄哨兵衛(wèi)頭結(jié)點的下一節(jié)點
ListNode* next = pHead->next;
//構(gòu)建各節(jié)點之間的關(guān)系
pHead->next = newnode;
newnode->prev = pHead;
newnode->next = next;
next->prev = newnode;
return;
}
頭刪鏈表
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
//斷言傳入指針不為NULL
assert(pHead);
//只剩哨兵衛(wèi)頭結(jié)點的情況
if (pHead->next == pHead)
return;
//記錄哨兵衛(wèi)頭結(jié)點下一節(jié)點及其的下一節(jié)點
ListNode* next = pHead->next;
ListNode* nextNext = next->next;
//釋放節(jié)點
free(next);
pHead->next = nextNext;
nextNext->prev = pHead;
return;
}
查找鏈表
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
//斷言傳入指針不為NULL
assert(pHead);
//創(chuàng)建尋址指針
ListNode* cur = pHead->next;
while (cur != pHead)
{
//比較數(shù)據(jù)
if (cur->data == x)
return cur;
//找到下一個節(jié)點
cur = cur->next;
}
//沒找到則返回NULL
return NULL;
}
鏈表pos位置的刪除
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
return;
}
總結(jié)
我們在實帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單現(xiàn)的時候可以看出其實帶頭雙向循環(huán)鏈表實現(xiàn)起來并不難，而且在雙向循環(huán)特點的加持下，在一些方面顯得格外方便。
但是因為帶頭雙向循環(huán)鏈表結(jié)構(gòu)的復(fù)雜性，我們通常還是會使用邏輯結(jié)構(gòu)相對簡單的單鏈表，并且在oj題上考的最多的也是單鏈表。
但我們?nèi)砸炀氄莆諑ь^雙向循環(huán)鏈表的結(jié)構(gòu)和實現(xiàn)方式，因為這是一種特別且方便的結(jié)構(gòu)，且用處十分強大。
原文鏈接：https://blog.csdn.net/yin_ming_hui/article/details/123607952
相關(guān)推薦
- 2022-06-01 C語言超詳細(xì)講解字符串相乘_C 語言
- 2022-04-25 基于Matplotlib?調(diào)用?pyplot?模塊中?figure()?函數(shù)處理?figure圖形對
- 2022-12-13 詳解如何魔改Retrofit實例_Android
- 2022-06-22 Github創(chuàng)建個人訪問Tokens令牌_其它綜合
- 2023-05-14 opencv繪制矩形和圓的實現(xiàn)_python
- 2023-02-18 減少react組件不必要的重新渲染實現(xiàn)方法_React
- 2022-05-02 Python中的變量和數(shù)據(jù)類型詳情_python
- 2022-04-03 Python?webargs?模塊的簡單使用_python
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速