前引：今天學習的雙鏈表屬于鏈表結構中最復雜的一種（帶頭雙向循環鏈表），按照安排，我們會先進行復習，如何實現雙鏈表，如基本的頭插、頭刪、尾刪、尾插，掌握每個細節，隨后進行例題練習，幫助我們了解它的實際挑戰，前面的實現只是了解它結構的入門，當然只有打好基礎才是最重要的，小編會仔細講解它的各個環節，正文開始~?

目錄

知識點速覽

雙鏈表的實現

節點結構

設置哨兵節點

?開辟節點

?尾插

尾刪

頭插

頭刪

?在目標節點前面插入

在目標節點后面插入

練習題說明

---

知識點速覽

雙鏈表的實現

今天咱們來復習一下最復雜的鏈表結構——帶頭雙向循環鏈表。根據字面意思我們大概可以詳細想象出來它的特點，首先有一個哨兵節點來充當頭節點，其次是循環雙向的，邏輯結構如下圖：

它較與單鏈表的結構里面多了一個指針，指向它的前一個節點，以此達到雙向。針對哨兵節點：

哨兵節點一般不存儲任何數據，?不僅使用方便，可以簡化插入刪除的操作（不用傳二級指針），所有操作無需去處理哨兵節點，邏輯統一，最后可以減少空指針異常

這里的循環是根據節點的空間結構而來的：頭節點->prev=尾節點，尾節點->next=頭節點

節點結構

較單鏈表而言只多加了一個指針，用來指向自身的前一個節點。這里小編用 tpedef 重定義了一下數據類型，方便以后進行維護。

typedef int Plastic;typedef struct DoubleList
{//數據域Plastic data;//前指針域struct DoubleList* prev;//后指針域struct DoubleList* next;
}DoubleList;

設置哨兵節點

哨兵節點的數據域一般不存儲數據，但是它之后的鏈表節點需要給一個數據作為參數開辟節點，所以小編在這里將二者分開，給哨兵節點單獨設置一個函數來開辟空間。開始時頭指針指向哨兵節點，哨兵節點前后指針應該指向自己，已達到雙向循環結構

//設置哨兵節點
DoubleList* pphead = Sentry();

//設置哨兵節點
DoubleList* Sentry()
{//開辟節點DoubleList* newnode = (DoubleList*)malloc(sizeof(DoubleList));//判斷空間有效性if (newnode == NULL){printf("哨兵節點開辟失敗\n");return NULL;}//初始化newnode->next = newnode;newnode->prev = newnode;return newnode;
}

?開辟節點

開辟節點還是和單鏈表一樣，傳一個數據給它就行了

這里需要注意：初始化開辟的節點時應該是前后指向自己的，如下圖：

//新增節點
DoubleList* Newnode(Plastic data)
{//開辟節點DoubleList* newnode = (DoubleList*)malloc(sizeof(DoubleList));//判斷空間有效性if (newnode == NULL){printf("節點開辟失敗\n");return NULL;}//初始化newnode->next = newnode;newnode->prev = newnode;newnode->data = data;return newnode;
}

?尾插

尾插需要先找尾，對于雙向循環鏈表而言，頭節點的前一個節點就是它的尾。然后再插入新增的節點，連接? next? 與? prev? 的關系即可

注意：尾插不用判斷鏈表是否存在啊，因為我們這里有哨兵節點，直接找尾、插入即可

//尾插
void Tail_insert(DoubleList* pphead, Plastic data)
{//找尾DoubleList* tail = pphead->prev;//開辟節點DoubleList* newnode = Newnode(data);//連接pphead->prev = newnode;newnode->next = pphead;tail->next = newnode;newnode->prev = tail;
}

下面我們通過打印函數來看一下尾插的效果如何：

//打印
void List_Print(DoubleList* pphead)
{//如果只有哨兵節點if (pphead->next == pphead){printf("無元素可以打印\n");return;}//因為如果只有哨兵節點，pphead->next就越界了DoubleList* first = pphead->next;while (first != pphead){printf("%d -> ", first->data);first = first->next;}printf("pphead\n");
}

尾刪

尾刪需要先找尾，然后將頭節點與尾的前一個節點進行連接，再釋放之前標記的尾，思維上并不難

//尾刪
void Tail_deletion(DoubleList* pphead)
{//如果只有頭節點無法刪除if (pphead->prev == pphead){printf("無法刪除\n");return;}//找尾DoubleList* tail = pphead->prev;//找倒數第二個節點DoubleList* cur = pphead->prev->prev;//更新關系，重新連接pphead->prev = cur;cur->next = pphead;free(tail);tail = NULL;
}

頭插

先標記頭節點的下一個節點，然后在頭節點與這個標記的節點中間插入即可，最后更新連接關系

//頭插
void Head_insert(DoubleList* pphead, int data)
{//標記頭節點的下一個節點DoubleList* first = pphead->next;DoubleList* newnode = Newnode(5);//更新連接關系pphead->next = newnode;newnode->next = first;first->prev = newnode;newnode->prev = pphead;
}

頭刪

對于只有哨兵節點的雙鏈表是無法頭刪的，因此需要先進行判斷。其次是標記鏈表的第一個節點、第二個節點，重新確立頭節點和第二個節點的關系，再釋放掉第一個節點

//頭刪
void Head_deletion(DoubleList* pphead)
{//判斷是否只有哨兵節點if (pphead->prev == pphead){printf("無法刪除\n");return;}//標記第一個節點DoubleList* first = pphead->next;//標記第二個節點DoubleList* second = first->next;//重新確立頭節點和第二個節點的關系pphead->next = second;second->prev = first;//釋放第一個節點free(first);first = NULL;
}

?在目標節點前面插入

我們先找到目標節點，然后再標記目標節點前面的一個節點，再確立三者之間的 next 與 prev 的關系，如下圖：

//在目標節點前面插入
void Before_target(DoubleList* pphead, int  data)
{//找目標節點DoubleList* cur = pphead->next;while (cur->data != data){if (cur == pphead){printf("沒有找到\n");return;}cur = cur->next;}//標記cur前面的節點DoubleList* prev = cur->prev;DoubleList* newnode = Newnode(6);//將三者進行連接prev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;
}

在目標節點后面插入

先找到目標節點，然后標記目標節點后面的一個節點，再確立新增節點、目標節點、標記節點的 next? prev 的關系，與“在目標節點前面插入”很類似

//在目標節點后面插入
void Behind_target(DoubleList* pphead, int data)
{//找目標節點DoubleList* cur = pphead->next;while (cur->data != data){if (cur == pphead){printf("沒有找到\n");return;}cur = cur->next;}//標記cur后面的節點DoubleList* next = cur->next;DoubleList* newnode = Newnode(7);//將三者進行連接cur->next = newnode;newnode->prev = cur;newnode->next = next;next->prev = newnode;
}

練習題說明

一般鏈表題，比如考研、面試、校招會以單鏈表居多，大家可以看我的上一篇文章來學習鏈表題目