C語言編程數據結構帶頭雙向循環(huán)鏈表全面詳解
前言
上一篇數據結構專欄：C語言數據結構單鏈表接口函數全面講解教程
我們介紹了單鏈表的各個接口函數，大家可能會發(fā)現單鏈表存在一些缺陷：比如它一個節(jié)點要存儲數據+下一個節(jié)點地址，占用的空間要遠多于順序表；并且由于單鏈表是無法從后往前找的，如果你想進行尾刪這樣的操作，你必須從第一個節(jié)點往后找，你的時間復雜度一定是O（n）。
為了解決上面的一些缺陷，我們今天來介紹帶頭雙向循環(huán)鏈表
一、什么是帶頭循環(huán)雙向鏈表
這種鏈表會有一個哨兵位head節(jié)點指向d1,然后d1指向d2…這和單鏈表非常相似。
但和單鏈表最大的區(qū)別就是：這種鏈表的每個節(jié)點不僅會存儲下一個節(jié)點地址而且會存儲上一個節(jié)點的地址，然后尾節(jié)點會存儲一個指向哨兵位head的地址，然后哨兵位head會存儲一個指向尾結點的地址。
具體代碼如下：
typedef int LTDataType;//萬一以后需要改鏈表數據類型，可以直接在這里更改（int）
typedef struct ListNode
{
struct ListNode*next;
struct ListNode*prev;
LTDataType data;
}ListNode;//結構體重命名
示例：pandas 是基于NumPy 的一種工具，該工具是為了解決數據分析任務而創(chuàng)建的。
二、鏈表初始化
類似于上圖的效果，剛開始創(chuàng)建只有一個節(jié)點，它儲存的前地址和后地址都指向自己
代碼如下（示例）：
#include<stdlib.h>//malloc函數頭文件
ListNode* BuyListNode(LTDataType x)//創(chuàng)建一個節(jié)點
{
ListNode*newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
ListNode* ListInit()//鏈表初始化
{
ListNode*phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
ps：這里ListInit函數用的是返回值的方法，你也可以用二級指針傳參來進行初始化操作
三、鏈表接口函數
1.尾插
我們以上圖為例，原先鏈表的head節(jié)點的前驅指向3，然后3的后驅指向head節(jié)點，那在3后面怎么進行尾插呢？由于head節(jié)點里存放了3節(jié)點的地址，所以我們可以直接找到3節(jié)點，找到之后怎么辦?把head節(jié)點的前驅改成4節(jié)點地址，3節(jié)點后驅改為4節(jié)點地址，最后4節(jié)點后驅指向head節(jié)點。如下圖：
代碼如下（示例）：
#include<assert.h>//assert函數頭文件
void ListPushBack(ListNode*phead, LTDataType x)//尾插
{
assert(phead);//對傳過來的指針進行斷言,因為你要進行尾插至少得有個頭節(jié)點啊
//如果傳過來的是空指針會進行報錯
ListNode*tail = phead->prev;
ListNode*newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->data = phead;
phead->prev = newnode;
}
2.頭插
如上圖，先要在head和d1之間進行頭插，怎么操作？非常簡單，思路和尾插一模一樣
head的后驅指向newnode，newnode的前驅和后驅分別指向phead和d1，d1前驅指向newnode如下圖：
代碼如下（示例）：
void ListPushFront(ListNode*phead,LTDataType x)
{
assert(phead);
ListNode*first = phead->next;
ListNode*newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
注意！?。∵@里是先定義了一個first來存放d1這個地址，如果不事先定義的話，phead->next = newnode;head不再存儲d1地址，你就找不到d1了。當然了，如果你就是不想先定義一個first來存放d1地址也可以。怎么做呢？“先連后斷”，newnode后驅先接上d1節(jié)點，然后你head節(jié)點后驅接上newnode。
3.頭刪
頭刪也是和前面兩個類似的思想
頭刪也就是把d1節(jié)點刪掉，我們定義2個指針分別指向d1和d2，然后把head節(jié)點后驅接指向d2，d2前驅指向head即可，如下圖：
代碼如下（示例）：
void ListPopFront(ListNode*phead)
{
assert(phead);
ListNode*first = phead->next;
ListNode*second = first->next;
phead->next = second;
second->prev = phead;
}
4.尾刪
現在要刪除d3這個節(jié)點，我們定義一個tail和prev指針分別指向d3和d2，然后把d2后驅接上head，head前驅接上d2即可，如下圖：
代碼如下（示例）：
void ListPopBack(ListNode*phead)
{
assert(phead);
assert(phead->next != phead);//要進行尾刪至少保證有一個節(jié)點可刪（非head節(jié)點）
ListNode*tail = phead->prev;//頭節(jié)點前驅指向尾部
ListNode*prev = tail->prev;//通過尾部得到d2地址
prev->next = phead;//d2后驅head節(jié)點
phead->prev = prev;//head前驅指向d2節(jié)點
}
5.任意位置插入數據
要在某個位置前插入數據，你需要先找到那個位置在哪里，我們先寫一個查找函數
怎么個找法呢？很簡單，定義一個cur指針，然后從d1開始遍歷看有沒有我們想要找的數據，遍歷到head節(jié)點結束。
代碼如下（示例）：
ListNode* ListFind(ListNode*phead, LTDataType x)
{
assert(phead);
ListNode*cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;//遍歷完鏈表都沒有找到就返回空指針
}
找到所需位置后就是進行，插入操作
void ListInsert(ListNode*pos, LTDataType x)
{
assert(pos);
ListNode*prev = pos->prev;
ListNode*newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
兩個函數一起調用也是很簡單的，比如我現在要在鏈表里數據3的位置前插入300，下面兩行代碼即可完成兩個函數的運用。
ListNode*pos = ListFind(plist, 3); ListInsert(pos, 300);
ps:這里找到所需位置指針，你如果需要，也可以通過該指針對該位置的值進行修改，比如（返回的指針）->data=n
6.任意位置刪除數據
現在要刪除pos位置的數據，怎么操作？非常簡單！定義一個prev指向pos前一個節(jié)點，定義一個next指向pos后一個節(jié)點，然后prev和next連起來即可，如圖：
代碼如下（示例）：
void ListErase(ListNode*pos)//指定位置刪除
{
assert(pos);
ListNode*prev = pos->prev;
ListNode*next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);//prev和next連起來了，pos就可以被釋放掉了
}
四、打印鏈表
以上圖為例：要打印一個鏈表，head節(jié)點是不需要打印的，我們只需要打印存儲實際數據的d1，d2，d3即可，定義一個變量cur，讓它從d1開始遍歷，到head節(jié)點結束即可。
代碼如下（示例）：
void ListPrint(ListNode*phead)
{
ListNode*cur = phead->next;
while (cur != phead)
{
printf("%d\n", cur->data);
cur = cur->next;
}
printf("\n");
}
總結
本文介紹了帶頭循環(huán)雙向鏈表，包括其定義、各個接口函數、及其遍歷打印。雖然是鏈表中最復雜的結構，但它的代碼操作卻是最簡單的，希望通過今天的學習讀者能有所收獲~更多關于帶頭雙向循環(huán)鏈表數據結構的資料請關注腳本之家其它相關文章！
相關文章
本篇文章是對c語言中調試工具的用法進行了匯總，需要的朋友參考下2013-05-05
這篇文章主要介紹了關閉所有窗口的方法,原理是枚舉所有窗口句柄，然后發(fā)送WM_CLOSE消息來關閉窗口,需要的朋友可以參考下2014-01-01
這篇文章主要介紹了MFC列表控件CListCtrl使用方法示范,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-07-07
本文主要對紅黑樹進行了詳細介紹，并對其核心功能進行了模擬實現。文中的代碼對我們的學習或工作有一定的價值，感興趣的小伙伴可以了解一下2021-12-12
這篇文章主要介紹了C++11原子類型與原子操作的相關資料，幫助大家更好的理解和學習c++,感興趣的朋友可以了解下2020-08-08
這篇文章主要介紹了C++遞歸實現螺旋數組的實例代碼，代碼簡單易懂，非常不錯，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04
VS2019安裝配置MFC(安裝vs2019時沒有安裝mfc)
這篇文章主要介紹了VS2019安裝配置MFC(安裝vs2019時沒有安裝mfc)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
這篇文章主要介紹了c++ 智能指針基礎的相關資料，幫助大家更好的理解和學習使用c++，感興趣的朋友可以了解下，希望能給你帶來幫助2021-08-08
實例講解C++設計模式編程中State狀態(tài)模式的運用場景
這篇文章主要介紹了實例講解C++設計模式編程中State狀態(tài)模式的運用場景,文章最后的適用性部分則介紹了一些State模式善于處理的情況,需要的朋友可以參考下2016-03-03
C++名字空間是一種描述邏輯分組的機制,也就是說,如果有一些聲明按照某種準則在邏輯上屬于同一個模塊,就可以將它們放在同一個名字空間,以表明這個事實,這篇文章主要給大家介紹了關于C++語言中命名空間 (namespace)的相關資料,需要的朋友可以參考下2021-08-08