我们先来看看带头双向循环链表的结构：
看到这里我们可能会产生一个想法：这个链表看起来好复杂的样子，是不是它的增删改查比单链表更难写呢？嘿嘿，还真的不是这样的，双向链表的增删改查是很好写的哦！??
函数接口一览
初阶数据结构我们学习的一般都是增删改查这四种操作：
// 2、带头+双向+循环链表增删查改实现typedef int LTDataType;typedef struct ListNode{ LTDataType _data; struct ListNode* next; struct ListNode* prev;} ListNode;// 创建返回链表的头结点.ListNode* BuyListNode(LTDataType x);// 双向链表销毁void ListDestory(ListNode* phead);//双向链表的初始化ListNode* ListInit();// 双向链表打印void ListPrint(ListNode* phead);// 双向链表尾插void ListPushBack(ListNode* phead, LTDataType x);// 双向链表尾删void ListPopBack(ListNode* phead);// 双向链表头插void ListPushFront(ListNode* phead, LTDataType x);// 双向链表头删void ListPopFront(ListNode* phead);// 双向链表查找ListNode* ListFind(ListNode* phead, LTDataType x);// 双向链表在pos的前面进行插入void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的结点void ListErase(ListNode* pos);2. 函数接口的实现
2.1 ListNode* BuyListNode(LTDataType x)
这个函数存在的意义和单链表中的BuyListNo的函数一样哈。因为在尾插，头插，指定位置插入都需要向堆区申请空间，开辟节点，所以我们把它封装成一个函数。参数x用来给新的节点赋初值。代表你要开辟节点的data是多少。
//开辟新的节点ListNode* BuyNewNode(LTDataType x){ //malloc新的节点 ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); //开辟失败退出程序 if (newNode == NULL) { perror("BuyNewNode::malloc"); exit(-1); } else { //初始化新的节点，然后返回 newNode->data = x; newNode->prev = NULL; newNode->next = NULL; return newNode; }}2.2 void ListDestory(ListNode* phead)
因为链表的节点都是在堆区开辟的，所以在使用完链表后需要将其释放。释放空间的方式就是遍历整个链表，注意在释放一个节点时需要找到该节点的下一个节点，否则会导致内存泄漏！注意phead不可传入空指针，因此需要对phead进行断言。
这里的phead就是传说中的哨兵位的头结点，好处在写完整个双向链表后就能够和好的理解啦，哨兵位的头结点不存储任何数据的。你可以把他理解为一个很大的官，他是不需要亲自上战场的，负责指挥他的兵，有了他，他的兵能够更好的实现各种操作。或者你可以把他理解为王者荣耀中的辅助，有了他才能更好的取得游戏的胜利。
//销毁链表void ListDestory(ListNode* phead){ //断言phead assert(phead); ListNode* cur = phead->next; //遍历链表 while (cur != phead) { //找到下一个节点 ListNode* next = cur -> next; //释放节点 free(cur); //记录下一个要释放的节点 cur = next; } //释放哨兵位的头结点 free(phead); phead = NULL;}2.3 ListNode* ListInit()
初始化链表的函数就是开辟一个节点，让他作为哨兵位的头结点。然后让他的next，prev都指向自己。好处的话还需写代码的时候自己体会的哦！这样做的目的其实就是为了是头插，头删等操作统一化！还记得单链表写头插，头删函数时需要对特殊情况进行处理的痛苦吧！
//链表的初始化ListNode* ListInit(){ //因为哨兵位的头节点是不需要存储数据的，这个参数随便是啥都行 ListNode* phead = BuyNewNode(0); //prev,next均指向自己 phead->next = phead; phead->prev = phead; //返回哨兵位的头结点 return phead;}2.4 void ListPrint(ListNode* phead)
这个函数的实现也是很简单的哦！我们只需要遍历链表然后打印数据即可！同样不允许传入空指针，不然会发生空指针的解引用哦！这个不同于我们前面写过的单链表，单链表传入空指针说明链表为空！但这个双向链表经过初始化后就有一个哨兵位的头结点了！链表为空说明phead ->next = phead，或者phead->prev = phead。双链表为空的情况：
//双向链表的打印void ListPrint(ListNode* phead){ //断言 assert(phead); //如果是空链表可以打印一个空，判断空链表的方法上面降到了 //这里的话空链表就不做任何打印了 ListNode* cur = phead->next; while (cur != phead) { //用cur遍历双链表打印数据 printf("%d ", cur->data); cur = cur->next; } printf("\n");}2.5 void ListPushBack(ListNode* phead, LTDataType x)
还记得单链表尾插的痛苦嘛！需要对特殊情况进行处理，我们来看看谁双向链表需不需要对特殊情况进行处理！尾插肯定是要找到尾节点的撒，双链表找尾节点就直接phead->prev 就可以了！
当双向链表为空时：
尾节点：tail = phead->prev = phead 哈。
当双向链表不为空时：
同样地，找到尾节点 tail = phead->prev，用上面同样的方式画图！我们发现双链表不为空时也是找到尾节点，然后进行上面的四步操作！这就是双向链表，哨兵位的头结点，这样初始化链表的好处！
//双链表的尾插void ListPushBack(ListNode* phead, LTDataType x){ assert(phead); //调用接口申请节点即可 ListNode* newNode = BuyNewNode(x); //找到尾节点 ListNode* tail = phead->prev; //链接新的节点 tail->next = newNode; newNode->prev = tail; newNode->next = phead; phead->prev = newNode;}2.6 void ListPopBack(ListNode* phead)
删除节点时，同单链表没有数据不允许删除！双向链表判断为空的条件就是：phead->next = phead或者phead->prev = prev，我们只需要暴力断言即可！尾删的时候有两种删除方式哈！
记录尾节点并且记录尾节点的前一个节点。这样做就比较方便的，删除和链接不需要有任何的顺序。
只记录尾节点，那么就需要有一定的顺序啦！假设找到的尾节点是tail，删除顺序：
1：tail->prev->next = phead。
2：phead->prev = tail->prev。
3：释放尾节点tail。
我个人是比较喜欢第一种的哈！
//双向链表的尾删void ListPopBack(ListNode* phead){ assert(phead); //空链表不允许删除数据 assert(phead->next != phead); //找到两个节点 ListNode* tail = phead->prev; ListNode* pTail = tail->prev; //链接 pTail->next = phead; phead->prev = pTail; //释放 free(tail); tail = NULL;}2.7 void ListPushFront(ListNode* phead, LTDataType x)
双向链表的头插也是比较简单的哈！也不需要考虑特殊情况！如果不理解可以画画图就能够理解啦！
//双向链表的头插void ListPushFront(ListNode* phead, LTDataType x){ assert(phead); ListNode* newNode = BuyNewNode(x); //找到哨兵位的头结点的下一个节点 ListNode* next = phead->next; //找到next节点就随便链接就行 phead->next = newNode; newNode->next = next; newNode->prev = phead; next->prev = newNode;}2.8 void ListPopFront(ListNode* phead)
双向链表真的挺简单的，哈哈，不懂的话就画画图。
//双链表的头删void ListPopFront(ListNode* phead){ assert(phead); //链表没有数据不允许删除 assert(phead->next != phead); //依然找到要删除的节点，以及他的下一个节点 ListNode* delNode = phead->next; ListNode* next = delNode->next; //找到这个节点之后随便链接就行 next->prev = phead; phead->next = next; free(delNode); delNode = NULL;}2.9 ListNode* ListFind(ListNode* phead, LTDataType x)
查找的函数和单链表的一模一样，遍历链表找到data值相同的节点即可！这个函数主要是配合指定位置删除和插入的函数使用的！
//双链表的查找ListNode* ListFind(ListNode* phead, LTDataType x){ asset(phead); //用cur遍历链表 ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } //没找到返回空指针 return NULL;}2.10 void ListInsert(ListNode* pos, LTDataType x)
这个函数是在指定节点的位置之前插入一个新的节点哈，pos位置的节点通过LIstFind函数找到。我们只需要找到pos位置之前的那个节点，然后与newNode进行连接即可！当然不用找到pos的前一个节点也行的！
//双链表指定位置之前插入新节点void ListInsert(ListNode* pos, LTDataType x){ //如果ListFind函数返回的空指针，pos就是空指针，需要断言 assert(pos); //开辟新节点 ListNode* newNode = BuyNewNode(x); //找到前一个节点 ListNode* prev = pos->prev; //连接 prev->next = newNode; newNode->prev = prev; newNode->next = pos; pos->prev = newNode;}2.11 void ListErase(ListNode* pos)
和指定位置之前的插入一样，ListErase函数也是需要ListFind函数配合使用的！我们只需要找到pos位置的前一个节点，后一个节点，然后连接即可！
//删除指定位置的节点void ListErase(ListNode* pos){ //如果ListFind函数返回的空指针是不允许删除的 assert(pos); //找到前一个和后一个节点 ListNode* prev = pos->prev, * next = pos->next; //链接 prev->next = next; next->prev = prev; //释放节点 free(pos); pos = NULL;}3. 一个小小的技巧
在我们有了指定位置之前插入和删除的函数之后！头插，头删，尾插，尾删都可以使用这两个函数来替代啦！
头插：就是在phead->next 位置之前插入。
头删：就是删除 phead->next位置的节点。
尾插：就是在phead的位置插入一个新节点。
尾删：就是删除phead->prev位置所在的节点。
有了这个小技巧20min手撕双向带头循环链表！
4. 顺序表链表总结
不同点 | 顺序表 | 链表 |
存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定 连续 |
随机访问 | 支持O(1) | 不支持：O(N) |
任意位置插入或者删除 元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指针指向 |
插入 | 动态顺序表，空间不够时需要 扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |