目錄

一、雙向帶頭循環鏈表

概念

?二、哨兵位的頭節點

優點：

頭節點的初始化

三、帶頭雙向鏈表的實現

1.雙鏈表的銷毀

2.雙鏈表的打印

3.雙鏈表的尾插和頭插

尾插：

頭插：

4.雙鏈表的尾刪和頭刪

尾刪：

頭刪：

5.雙鏈表的查找

四、測試代碼

---

一、雙向帶頭循環鏈表

概念

? ? ? ? 名如其實，這個鏈表結構有哨兵位頭節點，雙向并且循環，結構最復雜。一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶 來很多優勢，實現反而簡單了，后面我們代碼實現了就知道了這里我們用一張圖片就能很好的看清楚雙向帶頭循環鏈表的結構了。

?二、哨兵位的頭節點

? ? ? ? 從上一篇文章我們就在說帶頭/不帶頭，那么這個頭是什么呢？其實它就是哨兵位的頭節點。這個節點一般在一個鏈表的最前方的位置，不用來儲存數據。

優點：

1.?? ?簡化邊界條件處理：
??? ?在沒有哨兵節點的情況下，鏈表的頭插、頭刪等操作需要特別處理頭節點為空的情況。
??? ?使用哨兵節點后，頭節點始終存在，簡化了插入和刪除操作的邏輯，不需要單獨處理頭節點為空的情況。

2.?? ?統一操作邏輯：
??? ?無論是頭插、尾插、頭刪還是尾刪，操作邏輯都可以統一處理，不需要區分是否是第一個節點。
??? ?例如，插入操作總是插入到哨兵節點之后，刪除操作總是刪除哨兵節點之后的節點。

3.?? ?提高代碼可讀性和維護性：
??? ?由于邊界條件處理簡化，代碼邏輯更加清晰，減少了出錯的可能性。
??? ?代碼維護起來也更加方便，因為不需要在多個地方處理特殊情況。
4.?? ?便于實現某些算法：
??? ?在某些算法中，使用哨兵節點可以避免多次檢查鏈表是否為空的情況，提高算法的效率。

頭節點的初始化

// 創建返回鏈表的頭結點.
ListNode* ListCreate()
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = 0;newnode->next = newnode;newnode->prev = newnode;return newnode;
}

三、帶頭雙向鏈表的實現

1.雙鏈表的銷毀

? ? ? ? 與單鏈表的銷毀類似，需要定義一個指針來遍歷整個鏈表，但是注意，如果是從頭節點開始遍歷，我們會因為無法很好的控制停止條件而導致無限循環，所以我們從頭節點的下一個開始遍歷，當這個cur指針指向頭節點時就停止，這里后面還會反復用到，請務必想清楚。

// 雙向鏈表銷毀
void ListDestory(ListNode* plist)
{assert(plist);ListNode* cur = plist->next;while (cur != plist){ListNode* next = cur->next;free(cur);cur = next;}free(plist);plist = NULL;
}

2.雙鏈表的打印

// 雙向鏈表打印
void ListPrint(ListNode* plist)
{ListNode* cur = plist->next;while (cur != plist){printf("%d<=>",cur->data);cur = cur->next;}printf("NULL\n");
}

3.雙鏈表的尾插和頭插

尾插：

// 雙向鏈表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{// 雙向鏈表的找尾很簡單，只需要指向plist的前一個節點就行ListNode* newnode = buyNewnode(x);ListNode* tail = plist->prev;tail->next = newnode;newnode->prev = tail;newnode->next = plist;plist->prev = newnode;
}

頭插：

// 雙向鏈表頭插
void ListPushFront(ListNode* plist, LTDataType x)
{assert(plist);ListNode* newnode = buyNewnode(x);ListNode* head = plist->next;plist->next = newnode;newnode->prev = plist;newnode->next = head;head->prev = newnode;
}

4.雙鏈表的尾刪和頭刪

尾刪：

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

頭刪：

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

5.雙鏈表的查找

// 雙向鏈表查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{assert(plist);ListNode* cur = plist->next;while (cur != plist){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

四、測試代碼

// 2、帶頭+雙向+循環鏈表增刪查改實現
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next; struct ListNode* prev;
}ListNode;
// 創建返回鏈表的頭結點.
ListNode* buyNewnode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
ListNode* ListCreate()
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = 0;newnode->next = newnode;newnode->prev = newnode;return newnode;
}
// 雙向鏈表銷毀
void ListDestory(ListNode* plist)
{assert(plist);ListNode* cur = plist->next;while (cur != plist){ListNode* next = cur->next;free(cur);cur = next;}free(plist);plist = NULL;
}
// 雙向鏈表打印
void ListPrint(ListNode* plist)
{ListNode* cur = plist->next;while (cur != plist){printf("%d<=>",cur->data);cur = cur->next;}printf("NULL\n");
}
// 雙向鏈表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{// 雙向鏈表的找尾很簡單，只需要指向plist的前一個節點就行ListNode* newnode = buyNewnode(x);ListNode* tail = plist->prev;tail->next = newnode;newnode->prev = tail;newnode->next = plist;plist->prev = newnode;
}
// 雙向鏈表尾刪
void ListPopBack(ListNode* plist)
{assert(plist);if (plist->next == plist){return;}ListNode* tail = plist->prev;ListNode* prev = tail->prev;free(tail);tail = NULL;prev->next = plist;plist->prev = prev;
}
// 雙向鏈表頭插
void ListPushFront(ListNode* plist, LTDataType x)
{assert(plist);ListNode* newnode = buyNewnode(x);ListNode* head = plist->next;plist->next = newnode;newnode->prev = plist;newnode->next = head;head->prev = newnode;
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* plist)
{assert(plist);if (plist->next = plist){return;}ListNode* head = plist->next;ListNode* newHead = head->next;free(head);head = NULL;plist->next = newHead;newHead->prev = plist;
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{assert(plist);ListNode* cur = plist->next;while (cur != plist){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
int main()
{ListNode* plist = ListCreate();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPushFront(plist, 0);ListPrint(plist);ListPopFront(plist);ListPrint(plist);return 0;
}