前言
數(shù)據(jù)結(jié)構(gòu)入門 — 雙向鏈表詳解
博客主頁鏈接：https://blog.csdn.net/m0_74014525
關(guān)注博主，后期持續(xù)更新系列文章
文章末尾有源碼*****感謝觀看，希望對(duì)你有所幫助*****
系列文章
第一篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_單鏈表
第二篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_雙向鏈表
第三篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_循環(huán)鏈表
什么是雙向鏈表
雙向鏈表（Doubly Linked List）是一種鏈表數(shù)據(jù)結(jié)構(gòu)，它的每個(gè)節(jié)點(diǎn)都含有兩個(gè)指針，一個(gè)指向前一個(gè)節(jié)點(diǎn)，一個(gè)指向后一個(gè)節(jié)點(diǎn)。相比較于單向鏈表，雙向鏈表可以雙向遍歷，即可以從頭到尾或從尾到頭遍歷鏈表。在雙向鏈表中，每個(gè)節(jié)點(diǎn)包含兩個(gè)指針域和一個(gè)數(shù)據(jù)域。其中，一個(gè)指針指向前驅(qū)節(jié)點(diǎn)，另一個(gè)指針指向后繼節(jié)點(diǎn)。這兩個(gè)指針使得雙向鏈表的插入、刪除等操作不需要像單向鏈表那樣需要遍歷整個(gè)鏈表來尋找前驅(qū)節(jié)點(diǎn)，提高了鏈表的操作效率。
概念與結(jié)構(gòu)（圖文）
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。
雙向鏈表與單鏈表的區(qū)別
雙向鏈表和單鏈表是兩種不同的鏈表結(jié)構(gòu)。
單向鏈表是一種鏈表，在每個(gè)節(jié)點(diǎn)中包含指向下一個(gè)節(jié)點(diǎn)的指針。這意味著在單向鏈表中，節(jié)點(diǎn)只能從頭開始遍歷到尾部。在單向鏈表中，每個(gè)節(jié)點(diǎn)只存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針，而不存儲(chǔ)指向前一個(gè)節(jié)點(diǎn)的指針。
雙向鏈表是一種鏈表，在每個(gè)節(jié)點(diǎn)中包含指向下一個(gè)節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)的指針。這意味著在雙向鏈表中，節(jié)點(diǎn)可以被從頭到尾或從尾到頭遍歷。在雙向鏈表中，每個(gè)節(jié)點(diǎn)存儲(chǔ)指向前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的指針。
因此，雙向鏈表可以更方便地進(jìn)行雙向遍歷，但是需要更多的內(nèi)存空間來存儲(chǔ)每個(gè)節(jié)點(diǎn)的兩個(gè)指針。相比之下，在單向鏈表中，只需要一個(gè)指針來指向下一個(gè)節(jié)點(diǎn)，因此內(nèi)存占用量更小。
帶頭雙向循環(huán)鏈表接口實(shí)現(xiàn)（代碼演示）
帶頭+雙向+循環(huán)鏈表增刪查改實(shí)現(xiàn)
1. 動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)
typedef int STDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
STDataType data;
}LTNode;
雙向鏈表打印
void LTPrint(LTNode* phead)
{
assert(phead);
printf("phead<->");
//跳過哨兵位
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
printf("\n");
}
增刪查改接口
根據(jù)增刪查改順序編排
雙向鏈表頭插：
//頭插
void LTPushFront(LTNode* phead, STDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
LTNode* first = phead->next;
newnode->next = first;
first->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
雙向鏈表尾插：
//尾插
void LTPushBack(LTNode* phead, STDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
//找到最后一個(gè)
LTNode* tail = phead->prev;
newnode->prev = tail;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;
}
雙向鏈表頭刪：
//頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}
雙向鏈表尾刪:
//尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
free(tail);
phead->prev = tailprev;
tailprev->next = phead;
}
查找：
LTNode* LTFind(LTNode* phead, STDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
在指點(diǎn)位置插入：
void LTInsert(LTNode* pos, STDataType x)
{
LTNode* newnode = BuyLTNode(x);
LTNode* posprev = pos->prev;
newnode->next = pos;
pos->prev = newnode;
posprev->next = newnode;
newnode->prev = posprev;
}
在指點(diǎn)位置刪除：
// 把pos刪除
void LTErase(LTNode* pos)
{
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
free(pos);
posprev->next = posnext;
posnext->prev = posprev;
}
雙向鏈表銷毀
void LTDestory(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
五、所有文件代碼
1. Gitee鏈接
***查看所有代碼***
點(diǎn)擊右邊藍(lán)色文字 DuckBro Gitee 代碼倉庫
總結(jié)
帶頭雙向循環(huán)鏈表的基本概念和常見操作。帶頭雙向循環(huán)鏈表是一種特殊的雙向鏈表，它多了一個(gè)頭節(jié)點(diǎn)和一個(gè)尾節(jié)點(diǎn)，并且首尾相連形成一個(gè)環(huán)。
這樣可以實(shí)現(xiàn)循環(huán)遍歷鏈表。在帶頭雙向循環(huán)鏈表中，插入、刪除節(jié)點(diǎn)等操作都有特殊處理方式。帶頭雙向循環(huán)鏈表在實(shí)際應(yīng)用中比較常見，如操作系統(tǒng)中的進(jìn)程管理、音樂播放器中的播放列表等。文章來源：http://www.zghlxwxcb.cn/news/detail-672436.html
如這篇博客對(duì)大家有幫助的話，希望 三連 支持一下 ?。。?如果有錯(cuò)誤感謝大佬的斧正 如有 其他見解發(fā)到評(píng)論區(qū)，一起學(xué)習(xí) 一起進(jìn)步。文章來源地址http://www.zghlxwxcb.cn/news/detail-672436.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
