????????????????
????????????????
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追風趕月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平蕪盡處是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
????????????????
????????????????

🍌雙向鏈表的定義與結構

雙向鏈表：雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。（兩個指針就是一個指向下一個數據，另一個指針指向上一個數據。如圖中head頭指針和tail尾指針）

在雙向鏈表中還有一個特殊點，就是頭指針，雙向鏈表是帶頭的。在上次我們說的單鏈表中是不帶頭的，一旦涉及到頭，我們就是先判斷是不是為空，而在雙向鏈表中就是不會涉及到這個問題了，不用再去一個一個的判斷，就會省去很多的麻煩。

帶頭的雙向鏈表嘴尾常用，所以我們這里就介紹帶頭的雙向鏈表

🍌雙向鏈表增刪查改（有頭+雙向+循環鏈表增刪查改實現）

🍍其它接口

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int LTdatetype;typedef struct ListNode
{LTdatetype date;struct ListNode* next;struct ListNode* tail;
}ListNode;

定義一些接口

🍍創建返回鏈表的頭結點

//創建返回鏈表的頭結點
ListNode* Create(LTdatetype x)
{ListNode* cur =(ListNode*)malloc(sizeof(ListNode));if (cur == NULL){perror("malloc  faild");exit(-1);}cur->next = NULL;cur->tail = NULL;cur->date = x;return cur;
}ListNode* Inia()
{ListNode* node = Create(0);node->next = node;node->tail = node;return node;
}

Create函數就是創建一個節點。而Inia函數本來是進行初始化，而想要變成循環的鏈表，形參改變實參那就要用到二級指針，因為這里是雙向鏈表，涉及頭指針的時候不需要考慮二級指針，所以在這里就只有初始化需要用到頭指針，所以我們就干脆用返回值，這樣就不看起來違和了，當然用二級指針也沒有什么問題，看自己習慣即可。

🍍雙向鏈表銷毀

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

🍍雙向鏈表打印

// 雙向鏈表打印
void Print(ListNode* ps)
{assert(ps);ListNode* cur = ps->next;while (cur != ps){printf("%d<=>", cur->date);cur = cur->next;}
}

在這里打印，我們就不能使用和單鏈表打印的方法了，因為我們這里是循環鏈表，并且我們的ps里面沒有存有數據，所以我們要從ps的下個數據開始，也就是圖中cur的位置，然后在cur到ps的時候跳出循環就可以了。

🍍雙向鏈表尾插

// 雙向鏈表尾插
void LTpushbake(ListNode* ps, LTdatetype x)
{assert(ps);ListNode* cur = Create(x);ListNode *node = ps->tail ;//ps的頭要指向curnode->next = cur;//cur的尾要指向pscur->tail = node;//ps的尾要指向curps->tail = cur;//cur的頭要指向pscur->next = ps;
}

之所以要這樣的指向，是因為這是一個循環的雙向鏈表。

🍍雙向鏈表尾刪

// 雙向鏈表尾刪
void LTpopbake(ListNode* ps)
{assert(ps);assert(ps->next != ps);ListNode* cur = ps->tail;ListNode* curtail = cur->tail;free(cur);cur->next = cur->tail = NULL;curtail->next = ps;ps->tail = curtail;}

在這里因為這是循環鏈表所以不用遍歷去找尾結點，當然用遍歷也是可以的

🍍雙向鏈表頭插

// 雙向鏈表頭插
void LTpushfront(ListNode* ps, LTdatetype x)
{assert(ps);ListNode* node = Create(x);ListNode* cur = ps->next;ps->next = node;node->tail = ps;node->next = cur;cur->tail = node;}

在帶頭的鏈表中，頭插是最方便的，不用像不帶頭的單鏈表中一個一個去判斷，大大的節省了我們的時間

🍍雙向鏈表頭刪

// 雙向鏈表頭刪
void LTpopfront(ListNode* ps)
{assert(ps);assert(ps->next != ps);ListNode* node = ps->next;ListNode* node_next = node->next;free(node);ps->next = node_next;node_next->tail = ps;
}

在帶頭的鏈表中，頭刪也很方便了。

🍍雙向鏈表查找

// 雙向鏈表查找
ListNode * LTfind(ListNode* ps, LTdatetype x)
{assert(ps);ListNode* cur = ps->next;while (cur != ps){if (cur->date == x){return cur;}cur = cur->next;}return NULL;
}

關于這個查找還是要注意下，因為我們這里是循環鏈表，所以要注意記得要設置跳出循環的條件。

🍍雙向鏈表在pos的前面進行插入

// 雙向鏈表在pos的前面進行插入
void LTinsert(ListNode *pos, LTdatetype x)
{assert(pos);ListNode* node = Create(x);ListNode* pos_tail = pos->tail;pos_tail->next = node;node->tail = pos_tail;node->next = pos;pos->tail = node;}

在pos前插入和頭插，尾插差不多的意思

🍍雙向鏈表刪除pos位置的節點

// 雙向鏈表刪除pos位置的節點
void LTdelete(ListNode* pos)
{assert(pos);ListNode* pos_tail = pos->tail;ListNode* pos_next = pos->next;free(pos);pos_tail->next = pos_next;pos_next->tail = pos_tail;
}

刪除pos位置，也差不多和前面意思都差不多

🍌雙向鏈表整體代碼的實現

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int LTdatetype;//創建返回鏈表的頭結點
typedef struct ListNode
{LTdatetype date;struct ListNode* next;struct ListNode* tail;
}ListNode;ListNode* Create(LTdatetype x)
{ListNode* cur = (ListNode*)malloc(sizeof(ListNode));if (cur == NULL){perror("malloc  faild");exit(-1);}cur->next = NULL;cur->tail = NULL;cur->date = x;return cur;
}ListNode* Inia()
{ListNode* node = Create(0);node->next = node;node->tail = node;return node;
}// 雙向鏈表銷毀
void Destreoy(ListNode* ps)
{assert(ps);ListNode* cur = ps->next;while (cur != ps){cur = cur->next;free(cur->tail);}free(ps);
}// 雙向鏈表打印
void LTprint(ListNode* ps)
{assert(ps);ListNode* cur = ps->next;printf("ps<=>");while (cur != ps){printf("%d<=>", cur->date);cur = cur->next;}printf("\n");
}// 雙向鏈表尾插
void LTpushbake(ListNode* ps, LTdatetype x)
{assert(ps);ListNode* cur = Create(x);ListNode* node = ps->tail;node->next = cur;cur->tail = node;ps->tail = cur;cur->next = ps;
}// 雙向鏈表尾刪
void LTpopbake(ListNode* ps)
{assert(ps);assert(ps->next != ps);ListNode* cur = ps->tail;ListNode* curtail = cur->tail;free(cur);curtail->next = ps;ps->tail = curtail;}// 雙向鏈表頭插
void LTpushfront(ListNode* ps, LTdatetype x)
{assert(ps);ListNode* node = Create(x);ListNode* cur = ps->next;ps->next = node;node->tail = ps;node->next = cur;cur->tail = node;}// 雙向鏈表頭刪
void LTpopfront(ListNode* ps)
{assert(ps);assert(ps->next != ps);ListNode* node = ps->next;ListNode* node_next = node->next;free(node);ps->next = node_next;node_next->tail = ps;
}// 雙向鏈表查找
ListNode * LTfind(ListNode* ps, LTdatetype x)
{assert(ps);ListNode* cur = ps->next;while (cur != ps){if (cur->date == x){return cur;}cur = cur->next;}return NULL;
}// 雙向鏈表在pos的前面進行插入
void LTinsert(ListNode *pos, LTdatetype x)
{assert(pos);ListNode* node = Create(x);ListNode* pos_tail = pos->tail;pos_tail->next = node;node->tail = pos_tail;node->next = pos;pos->tail = node;}// 雙向鏈表刪除pos位置的節點
void LTdelete(ListNode* pos)
{assert(pos);ListNode* pos_tail = pos->tail;ListNode* pos_next = pos->next;free(pos);pos_tail->next = pos_next;pos_next->tail = pos_tail;
}void test1()//測試
{ListNode* ps = Inia();LTpushbake(ps, 1);//尾插LTpushbake(ps, 2);//尾插LTpushbake(ps, 3);//尾插LTpushbake(ps, 4);//尾插LTprint(ps);//打印LTpopbake(ps);//尾刪LTprint(ps);//打印LTpushfront(ps, 10);//頭插LTpushfront(ps, 11);//頭插LTpushfront(ps, 12);//頭插LTpushfront(ps, 13);//頭插LTprint(ps);//打印LTpopfront(ps);//頭刪LTprint(ps);//打印ListNode *pos = LTfind(ps, 11);//雙向鏈表查找if (pos == NULL){printf("沒找到\n");}else{printf("找到了，為：%d\n", pos->date);}LTinsert(pos, 100);// 雙向鏈表在pos的前面進行插入LTprint(ps);//打印LTdelete(pos);//雙向鏈表刪除pos位置的節點LTprint(ps);//打印Destreoy(ps);//雙向鏈表銷毀
}int main()
{test1();//測試return 0;
}

帶頭的雙向鏈表實現起來還是非常簡單的，大家如果對于文章中的某一個點有問題，歡迎私聊我。