一. 前言
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
二. 带头双向链表接口实现
1.准备工作
由于实际开发项目中，项目的实现都是采用模块化的方式实现。所以博主在这也采用了模块化的方式。
#pragma once typedef int LTDataType; typedef struct ListNode { struct ListNode* next;//下一个节点指针 struct ListNode* prev;//上一个节点指针 LTDataType data;//数据域 }LTNode;
为了后续函数功能实现过程中数据类型书写方便性，我们将struct ListNode重命名为LTNode。
同时后续好修改数据域类型，我们将数据域类型int重命名为LTDataType.
2. 创建一个节点
不管是后续插入数据还是初始化，我们都先要创建一个节点来存储数据。
所以我们在这设计了一个相关函数，从而避免大量重复的工作。
代码实现：
LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; }
三. 初始化
初始化时，我们支持需要创建一个节点作为哨兵位，并将两个指针同时指向自己即可。
代码实现：
LTNode* LTInit() { LTNode* phead = BuyLTNode(0); phead->next = phead; phead->prev = phead; return phead; }
4. 打印
打印比较简单。但需要注意我们是从哨兵位的下一个节点开始打印。
代码实现：
void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next;//哨兵位下一个节点 printf("phead<=>"); while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); }
5. 尾插
带头双链表的尾插比较简单。
我们通过哨兵位向前访问即可得到尾节点。在插入数据即可。
代码实现：
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev;//尾节点 LTNode* newnode = BuyLTNode(x);//要插入节点 //插入 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
6. 尾删
【代码思路】：尾删首先要判断是否还有节点可删。若有，找到尾节点以及尾节点的前一个结点。在释放尾节点，并将新的尾节点和哨兵位链接起来即可。
代码实现：
void LTPopBack(LTNode* phead) { assert(phead); assert(phead != phead->next);//还有节点可删 LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; }
7. 头插
要实现头插，首先要强调是插到哨兵位的后面。
【代码思路】：直接将哨兵位，哨兵位的下一个节点以及新节点链接起来即可。
代码实现：
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->next; LTNode* newnode = BuyLTNode(x); phead->next = newnode; newnode->prev = phead; newnode->next = tail; tail->prev = newnode; }
8. 头删
【代码思路】：头删和尾删一样，需要是否还有节点可删。若还有元素可删，需要保存哨兵位后面两个节点first、second。再释放掉first后，将哨兵位和second链接起来。
代码实现：
void LTPopFront(LTNode* phead) { assert(phead); assert(phead != phead->next); LTNode* first = phead->next; LTNode* second = first->next; free(first); phead->next = second; second->prev = phead; }
9. 计算节点个数
【代码思路】：首先保存哨兵位的下一个节点。然后开始向后遍历访问，每次个数加1，直到某节点的下一个节点指向哨兵位为止。
代码实现：
int LTSize(LTNode* phead) { LTNode* cur = phead->next; int count = 0; while (cur != phead) { count++; cur = cur->next; } return count; }
Tips:
- 可能有部分学者已经注意到或在一些书籍上看到过以下思路：哨兵位的数据域是随机值，是否可以将它用于记录节点个数。每次进行增删查改等操作时，对其进行加1/减1。不仅更加方便得知节点个数，同时还避免该接口的实现。
- 在这里博主不在这建议这样做，又或者说大部分情况是不能这样做的。原因在于：我们在本篇博客中，数据域为整型，可以用于记录节点个数大下。但在实际开发过程中，数据域可能存储的是浮点数或结构体什么的，那上述思路将导致结果错误。
10. 查找数据
【代码思路】：查找数据，从哨兵位的下一个节点开始，遍历查找。找到返回数据地址，否则返回空指针。
代码实现：
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; }
11. 在任意位置插入数据
【代码思路】：首先需要强调的是，不管是链表还是顺序表，插入数据默认都是前插，在这里也一样。插入数据、插入位置节点、以及前一个结点链接起来即可。
我们直接将
代码实现：
void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = BuyLTNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
12. 在任意位置删除数据
【代码思路】：将该位置前一个和后一个节点链接起来后，再将该位置节点释放。
代码实现：
void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; free(pos); posPrev->next = posNext; posNext->prev = posPrev; }
13. 销毁
由于上述节点都是动态开辟的，使用往后需要销毁，释放内存。
代码实现：
void LTDestory(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
四. 如何10分钟内完成一个完整双链表
在实际开发过程中，我们一般实现实现任意位置插入删除接口的。然后在头插/删和尾插/删等接口中，调用上述两个接口，从而快速达到目的。
List.h:
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode; LTNode* BuyLTNode(LTDataType x);//创建节点 LTNode* LTInit();//初始化 void LTPrint(LTNode* phead);//打印 //在pos之前插入x void LTInsert(LTNode* pos, LTDataType x); //删除pos位置节点 void LTErase(LTNode* pos); void LTPushBack(LTNode* phead, LTDataType x);//尾插 void LTPopBack(LTNode* phead);//尾删 void LTPushFront(LTNode* phead, LTDataType x);//头插 void LTPopFront(LTNode* phead);//头删 int LTSize(LTNode* phead);//节点大小 LTNode* LTFind(LTNode* phead, LTDataType x);//查找 void LTDestory(LTNode* phead);//销毁
List.c:
#include "List.h" LTNode* BuyLTNode(LTDataType x)//创建节点 { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; } LTNode* LTInit()//初始化 { LTNode* phead = BuyLTNode(0); phead->next = phead; phead->prev = phead; return phead; } void LTPrint(LTNode* phead)//打印 { assert(phead); LTNode* cur = phead->next; printf("phead<=>"); while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); } void LTInsert(LTNode* pos, LTDataType x)//任意位置插入 { assert(pos); LTNode* posPrev = pos->prev; LTNode* newnode = BuyLTNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; } void LTErase(LTNode* pos)//任意位置删除 { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; free(pos); posPrev->next = posNext; posNext->prev = posPrev; } void LTPushBack(LTNode* phead, LTDataType x)//尾插 { assert(phead); LTInsert(phead, x); } void LTPopBack(LTNode* phead)//尾删 { assert(phead); assert(phead != phead->next); LTErase(phead->prev); } void LTPushFront(LTNode* phead, LTDataType x)//头插 { assert(phead); LTInsert(phead->next, x); } void LTPopFront(LTNode* phead)//头删 { assert(phead); assert(phead != phead->next); LTErase(phead->next); } int LTSize(LTNode* phead)//节点大小 { LTNode* cur = phead->next; int count = 0; while (cur != phead) { count++; cur = cur->next; } return count; } 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 LTDestory(LTNode* phead)//销毁 { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
