單鏈表在之前的博客里已經詳細講解過了 （指路導航 無哨兵位單向非回圈鏈表），接下來講解的是 雙向帶頭回圈鏈表，
原始碼地址鏈接
注意：要轉圖請提前打招呼
一級指標還是二級指標？
首先我們要確定的問題是帶哨兵位的鏈表，需要傳啥型別的實參？
由圖見，因為帶哨兵位，不對phead進行修改，所以只需要傳一級指標，
結點結構體
// 帶頭+雙向+回圈鏈表增刪查改
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
函式介面
// 創建回傳鏈表的頭結點
LTNode* ListCreate();
// 雙向鏈表銷毀
void ListDestroy(LTNode* phead);
// 雙向鏈表列印
void ListPrint(LTNode* phead);
// 雙向鏈表尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(LTNode* phead);
// 雙向鏈表頭插
void ListPushFront(LTNode* phead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(LTNode* phead);
// 雙向鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(LTNode* pos, LTDataType x);
// 雙向鏈表洗掉pos位置的結點
void ListErase(LTNode* pos);
創建回傳鏈表的頭結點
開辟一個哨兵位結點，結點next和prev指向自己，
LTNode* ListCreate()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
phead->next = phead;
phead->prev = phead;
return phead;
}
雙向鏈表銷毀
- 鏈表要求逐個銷毀
- 因為這里傳的是一級指標，free了哨兵位后會使他成為野指標，需要在呼叫函式處置NULL，
void ListDestroy(LTNode* phead)
{
assert(phead);
// 逐個銷毀
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
雙向鏈表列印
逐個列印、注意結束條件即可，
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
雙向鏈表尾插
老套路、不廢話，
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
雙向鏈表尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead); // 不能洗掉哨兵位
LTNode* oldtail = phead->prev;
LTNode* newtail = oldtail->prev;
phead->prev = newtail;
newtail->next = phead;
free(oldtail);
}
雙向鏈表頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* first = phead->next;
LTNode* newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
雙向鏈表頭刪
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next, * second = first->next;
//phead first second
phead->next = second;
second->prev = phead;
free(first);
}
雙向鏈表查找
遍歷思想，
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
雙向鏈表在pos的前面進行插入
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prevnode = pos->prev;
LTNode* newnode = BuyListNode(x);
// prevnode newnode pos
prevnode->next = newnode;
newnode->prev = prevnode;
newnode->next = pos;
pos->prev = newnode;
}
雙向鏈表洗掉pos位置的結點
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* next = pos->next, * prev = pos->prev;
// prev pos next
prev->next = next;
next->prev = pos;
}
總結
帶頭雙向回圈鏈表：結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶來很多優勢，實作反而簡單了，
碼文不易，歡迎三連，筆芯感謝！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342203.html
標籤：其他
上一篇：資料結構---順序表、單鏈表