目錄

一、雙向帶頭循環鏈表概述

1.什么是雙向帶頭循環鏈表

2.雙向帶頭循環鏈表的優勢

3.雙向帶頭循環鏈表簡圖

二、雙向帶頭循環鏈表的增刪查改圖解及代碼實現

1.雙向帶頭循環鏈表的頭插

2.雙向帶頭循環鏈表的尾插

3.雙向帶頭循環鏈表的頭刪

4.雙向帶頭循環鏈表的尾刪

5.雙向帶頭循環鏈表在pos位置前插入節點

6.雙向帶頭循環鏈表刪除pos位置節點

---

一、雙向帶頭循環鏈表概述

1.什么是雙向帶頭循環鏈表

????????雙向：每個節點都帶有一個指向下一個節點的指針(next)和一個直向前一個節點的指針(prev)；

????????帶頭：即鏈表帶有哨兵位頭節點，該節點只包含兩個指針，不存儲有效數據；

????????循環：哨兵位頭節點有一個next指針指向第一個有效數據節點，還有一個prev指針指向哨兵位節點的前一個節點即鏈表的尾節點，因此實現了鏈表的循環；

????????雙向帶頭循環鏈表的節點類型：

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;

2.雙向帶頭循環鏈表的優勢

????????雙向帶頭循環鏈表不需要我們遍歷每個節點來找尾節點，對于鏈表的尾插而言就變得非常簡單。由于較單向非循環鏈表而言，雙向帶頭循環鏈表多了一個指向前一個節點的指針prev，所以在結構上較為復雜，但實際應用中少了很多的麻煩。

3.雙向帶頭循環鏈表簡圖

?

二、雙向帶頭循環鏈表的增刪查改圖解及代碼實現

1.雙向帶頭循環鏈表的頭插

示意圖：

代碼實現：

// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* NewNode = Node_New(x);ListNode* First = pHead->next;NewNode->next = First;First->prev = NewNode;NewNode->prev = pHead;pHead->next = NewNode;
}

2.雙向帶頭循環鏈表的尾插

示意圖：

代碼實現：

// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* NewNode = Node_New(x);ListNode* Tail = pHead->prev;NewNode->prev = Tail;Tail->next = NewNode;NewNode->next = pHead;pHead->prev = NewNode;
}

3.雙向帶頭循環鏈表的頭刪

示意圖：

代碼實現：

// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{assert(pHead);if (pHead->next == pHead){return;}ListNode* First = pHead->next;ListNode* Next = First->next;pHead->next = Next;Next->prev = pHead;free(First);First = NULL;
}

4.雙向帶頭循環鏈表的尾刪

示意圖：

代碼實現：

// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{assert(pHead);if (pHead->next == pHead){return;}ListNode* Tail = pHead->prev;ListNode* Prev = Tail->prev;Prev->next = pHead;pHead->prev = Prev;free(Tail);Tail = NULL;
}

5.雙向帶頭循環鏈表在pos位置前插入節點

示意圖：

代碼實現：

// 雙向鏈表在pos位置的前面插入節點
void ListInsert(ListNode* pos, LTDataType x)
{ListNode* NewNode = Node_New(x);ListNode* Prev = pos->prev;Prev->next = NewNode;NewNode->prev = Prev;NewNode->next = pos;pos->prev = NewNode;
}

6.雙向帶頭循環鏈表刪除pos位置節點

示意圖：

代碼實現：

// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos)
{ListNode* Prev = pos->prev;ListNode* Hind = pos->next;Prev->next = Hind;Hind->prev = Prev;free(pos);pos = NULL;
}