引:上次我们学习了单链表的实现，相对于双向循环链表来说，单链表的各中操作，比如说增删查改等都显得非常麻烦。所以接下来来学习一下双向循环链表吧！
💊1.双向循环链表：
💊1.1何为双向循环链表
如上所示：每个节点都有包含有两个指针域和一个数据域；
两个指针域一个存储前一个节点的地址，另一个存储下一个节点的地址；这种结构虽然看起来比单链表复杂一些，但是可以简化一系列后来的增删查改的操作；
💊1.2双向循环链表的实现
💊1.2.1结构体的创建
这个结构体的创建和单链表的结构体的创建是大同小异，我们需要两个指针域，一个数据域；
代码：
typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode;
💊1.2.2双向循环链表的初始化
LTNode* InitList(LTNode* Phead);
这个函数实现的双向循环链表的初始化功能，函数参数的话这边选择了一级指针和单链表的初始化函数不同，单链表所使用的是二级指针；而且初始化函数内部也有所不同；
代码：
//申请节点函数 LTNode* BuyListNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = node->prev = NULL; return node; } //初始化双向链表 LTNode* InitList(LTNode* phead) { phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; }
💊1.2.3双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
对于双向循环链表来说，它的尾插非常简单，因为它不需要去遍历链表来找到链表的尾部节点；
代码：
//双向链表的尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; phead->prev = newnode; newnode->next = phead; }
💊1.2.4双向链表的尾部删除
双向链表的尾部删除的和尾部插入同样简单，因为它不需要遍历链表，只需要进行相应的链接操作即可。
代码：
//双向链表的尾部删除 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; tailprev->next = phead; phead->prev = tailprev; free(tail); }
💊1.2.5双向链表的头插
链表的头插相对于单链表来说复杂程度不相上下，但也不难，因为有哨兵位节点的存在，在连接节点的时候还是相对方便的；
代码：
//双向链表的头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
💊1.2.6双向链表的数据的打印
函数的实现非常简单，简单的遍历链表即可，唯一需要注意到的点就是我们什么时候停下来；
代码：
//双向链表的打印 void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
💊1.2.7双向链表的头部删除数据
双向链表头部删除数据很简单，只需要将phead->next删除之后再将phead->next->next和phead链接起来即可；
代码：
void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != NULL); LTNode* first = phead->next; LTNode* second = first->next; free(first); phead->next = second; second->prev = phead; }
💊1.2.8双向链表寻找数据
方法和单链表是类似的，只是判断停止的条件不同；
代码：
//双向链表中寻找数据 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
💊1.2.9在双向链表的任意位置插入数据
这里我们实现的是在这个位置前进行插入数据，逻辑非常简单。
分两个步骤：①申请空间； ②链接节点；
代码：
//在双向链表的任意位置插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* pre = pos->prev; pre->next = newnode; newnode->prev = pre; newnode->next = pos; pos->prev = newnode; }
对此函数我们可以实现复用，重新构建头插和尾插：
//双向链表的头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next, x); } //双向链表的尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); }
💊1.2.10在双向链表的任意位置删除数据
这个函数我们实现的就是删除传入地址的节点，大的步骤也是分两个，先记录这个节点的前一个节点和后一个节点，然后free掉这个节点后，再链接；
代码：
//在双向链表的任意位置删除数据 void LTErase(LTNode* pos) { assert(pos); LTNode* pre = pos->prev; LTNode* next = pos->next; free(pos); pre->next = next; next->prev = pre; }
对此函数进行复用，改进头删和尾部删除函数：
代码：
//双向连边头部删除数据 void LTPopFront(LTNode* phead) { assert(phead); LTErase(phead->next); } //双向链表的尾部删除 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTErase(phead->prev); }
代码汇总：
#pragma once #include<stdio.h> #include<assert.h> #include<stdbool.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode; //初始化双向链表 LTNode* InitList(); //获取新的节点 LTNode* BuyListNode(LTDataType x); //双向链表的尾插 void LTPushBack(LTNode* phead, LTDataType x); //双向链表的尾部删除 void LTPopBack(LTNode* phead); //双向链表的头插 void LTPushFront(LTNode* phead, LTDataType x); //双向链表的打印 void LTPrint(LTNode* phead); //双向连边头部删除数据 void LTPopFront(LTNode* phead); //双向链表中寻找数据 LTNode* LTFind(LTNode* phead, LTDataType x); //在双向链表的任意位置插入和删除数据 void LTInsert(LTNode* pos, LTDataType x); void LTErase(LTNode* pos); //双向链表的判空 bool LTEmpty(LTNode* phead); //双向链表大小的计算 size_t LTSize(LTNode* phead); //双向链表的销毁 void LTDestroy(LTNode* phead); #define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" LTNode* BuyListNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = node->prev = NULL; return node; } //初始化双向链表 LTNode* InitList() { LTNode* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; } //双向链表的尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); //LTNode* newnode = BuyListNode(x); //LTNode* tail = phead->prev; //tail->next = newnode; //newnode->prev = tail; //phead->prev = newnode; //newnode->next = phead; LTInsert(phead, x); } //双向链表的尾部删除 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); //LTNode* tail = phead->prev; //LTNode* tailprev = tail->prev; //tailprev->next = phead; //phead->prev = tailprev; //free(tail); LTErase(phead->prev); } //双向链表的头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); //LTNode* newnode = BuyListNode(x); //newnode->next = phead->next; //phead->next->prev = newnode; //phead->next = newnode; //newnode->prev = phead; LTInsert(phead->next, x); } //双向链表的打印 void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } //双向连边头部删除数据 void LTPopFront(LTNode* phead) { assert(phead); //assert(phead->next != NULL); //LTNode* first = phead->next; //LTNode* second = first->next; //free(first); //phead->next = second; //second->prev = phead; LTErase(phead->next); } //双向链表中寻找数据 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在双向链表的任意位置插入和删除数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* pre = pos->prev; pre->next = newnode; newnode->prev = pre; newnode->next = pos; pos->prev = newnode; } void LTErase(LTNode* pos) { assert(pos); LTNode* pre = pos->prev; LTNode* next = pos->next; free(pos); pre->next = next; next->prev = pre; } //双向链表的判空 bool LTEmpty(LTNode* phead) { assert(phead); return phead->next != phead; } //双向链表大小的计算 size_t LTSize(LTNode* phead) { assert(phead); size_t x = 0; LTNode* cur = phead->next; while (cur != phead) { x++; cur = cur->next; } return x; } //双向链表的销毁 void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); } #define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" int main() { LTNode* phead = InitList(); LTPushBack(phead, 1); LTPushBack(phead, 2); LTPushBack(phead, 3); LTPushBack(phead, 4); LTPushBack(phead, 5); LTPrint(phead); LTPrint(phead); LTNode* x = LTFind(phead, 3); if (x) { x->data = 100; LTPrint(phead); } LTPopBack(phead); LTPrint(phead); printf("%d\n", LTSize(phead)); LTDestroy(phead); return 0; }
以上就是双向循环链表表的实现和各个函数需要注意的细节，如果有错误可以在评论区指正！
