前言

數(shù)據(jù)結(jié)構(gòu)入門 — 雙向鏈表詳解*
博客主頁鏈接：https://blog.csdn.net/m0_74014525
關(guān)注博主，后期持續(xù)更新系列文章
文章末尾有源碼
*****感謝觀看，希望對你有所幫助*****

---

系列文章

第一篇：數(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)，它的每個節(jié)點(diǎn)都含有兩個指針，一個指向前一個節(jié)點(diǎn)，一個指向后一個節(jié)點(diǎn)。相比較于單向鏈表，雙向鏈表可以雙向遍歷，即可以從頭到尾或從尾到頭遍歷鏈表。在雙向鏈表中，每個節(jié)點(diǎn)包含兩個指針域和一個數(shù)據(jù)域。其中，一個指針指向前驅(qū)節(jié)點(diǎn)，另一個指針指向后繼節(jié)點(diǎn)。這兩個指針使得雙向鏈表的插入、刪除等操作不需要像單向鏈表那樣需要遍歷整個鏈表來尋找前驅(qū)節(jié)點(diǎn)，提高了鏈表的操作效率。

概念與結(jié)構(gòu)（圖文）

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。

雙向鏈表與單鏈表的區(qū)別

雙向鏈表和單鏈表是兩種不同的鏈表結(jié)構(gòu)。

單向鏈表是一種鏈表，在每個節(jié)點(diǎn)中包含指向下一個節(jié)點(diǎn)的指針。這意味著在單向鏈表中，節(jié)點(diǎn)只能從頭開始遍歷到尾部。在單向鏈表中，每個節(jié)點(diǎn)只存儲指向下一個節(jié)點(diǎn)的指針，而不存儲指向前一個節(jié)點(diǎn)的指針。

雙向鏈表是一種鏈表，在每個節(jié)點(diǎn)中包含指向下一個節(jié)點(diǎn)和前一個節(jié)點(diǎn)的指針。這意味著在雙向鏈表中，節(jié)點(diǎn)可以被從頭到尾或從尾到頭遍歷。在雙向鏈表中，每個節(jié)點(diǎn)存儲指向前一個節(jié)點(diǎn)和下一個節(jié)點(diǎn)的指針。

因此，雙向鏈表可以更方便地進(jìn)行雙向遍歷，但是需要更多的內(nèi)存空間來存儲每個節(jié)點(diǎn)的兩個指針。相比之下，在單向鏈表中，只需要一個指針來指向下一個節(jié)點(diǎn)，因此內(nèi)存占用量更小。

帶頭雙向循環(huán)鏈表接口實(shí)現(xiàn)（代碼演示）

帶頭+雙向+循環(huán)鏈表增刪查改實(shí)現(xiàn)

1. 動態(tài)存儲結(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);//找到最后一個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)鏈表是一種特殊的雙向鏈表，它多了一個頭節(jié)點(diǎn)和一個尾節(jié)點(diǎn)，并且首尾相連形成一個環(huán)。

這樣可以實(shí)現(xiàn)循環(huán)遍歷鏈表。在帶頭雙向循環(huán)鏈表中，插入、刪除節(jié)點(diǎn)等操作都有特殊處理方式。帶頭雙向循環(huán)鏈表在實(shí)際應(yīng)用中比較常見，如操作系統(tǒng)中的進(jìn)程管理、音樂播放器中的播放列表等。

---

如這篇博客對大家有幫助的話，希望 三連 支持一下 ！！！ 如果有錯誤感謝大佬的斧正 如有 其他見解發(fā)到評論區(qū)，一起學(xué)習(xí) 一起進(jìn)步。