博客大纲
链表简介
链表有非常多的形式，目前主流的链表主要有三个区别：
1.是否有哨兵位
2.是否循环
3.单向还是双向
在此，我已经写过一篇单链表的博客：数据结构与算法：单链表。
在单链表中，我讲解了：不带哨兵位，单向，不循环链表。
而相应的为了将知识点讲全，本篇双链表博客讲述的是：带哨兵位，双向，循环链表。
本博客后续说的”单链表“与”双链表“都是以上两种链表。
对于单链表，主要用于初期学习数据结构时，提升对指针与结构体的理解就好，实战中不建议使用，因为其难度比双链表会高很多。而本博客的双链表，不仅书写难度低很多，而且使用起来效率也会高很多。
双链表
结构分析
在单链表中，我们使用了一个外部指针phead来存储头节点的指针，每个节点存着下一个节点的指针，最后一个节点存的指针为NULL。结构如下：
我们在此基础上，将双链表的结构一步一步推理出来：
哨兵位：
哨兵位，就是指在第一个节点中，不存放数据，只存放下一个节点的指针，作为一个头节点存在于链表中。
这样做的好处就是，能够极大降低assert与二级指针pphead的使用频率。而在单链表中，三大难点就是：assert，二级指针pphead，中间节点插入删除。使用哨兵位，就已经解决了两大问题。
使用哨兵位后，结构图如下：
在这个结构中，由于哨兵位不带数据，所以它也不能被用户访问。此时phead指向的就不是第一个节点了，而哨兵位的next指向的才是第一个节点。
双向链表：
双向链表是指，每个节点都存储着上一个节点和下一个节点两个指针，从而达到一个链表可以正向遍历，也可以逆向遍历，故称为双向。这样的话，我们就要修改我们的结构体，每个结构体内存两个指针，如下：
typedef int LTDataType;//方便后续修改数据类型 typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }ListNode;
prev指针指向前一个节点，next指针指向后一个节点。
结构图如下：
循环链表：
对于单链表而言，循环链表是指：尾部节点不指向NULL，而是指向头节点，如：
而对于双链表而言，循环是指：尾节点的next指针指向头节点，头部节点的prev指针指向尾节点，结构如下：
这就是我们双链表的最终结构了，在这个结构下，不论是代码书写还是用户体验都会优化不少，接下来我们开始实现每一个接口：
初始化接口
当这个双链表没有哨兵位以外的节点时，就是一个空链表，此时不论是链表的头还是尾，都是这个哨兵位，结果如下图：
对于双链表的初始化，即创建一个哨兵位头节点，但是此时链表中没有其它节点，所以要让其自循环。
即让这个哨兵位的prev与next都指向自己。
步骤如下：
1.开辟一个内存，存放哨兵位
2.哨兵位的prev与next指针都指向自己
//初始化 ListNode* LTInt() { ListNode* pHead = (ListNode*)malloc(sizeof(ListNode)); pHead->next = pHead; pHead->prev = pHead; return pHead; }
用户想要使用这个双链表时，只要调用这个函数，并接收其指针即可。
创建节点接口
此接口一般由各类插入接口调用，比如想在链表里插入一个数字3，用户就会使用插入接口。而在插入过程中，插入接口就需要为新数据创建节点。我们后续有三个插入接口，每个接口都写一遍创建空间的代码未免过于繁琐，故在此特地封装一个创建节点的函数。
由于我们创建节点的接口是独立出来的，它并不知到创建后它的前一个节点与后一个节点是啥，所以在开辟了一个节点后，其prev与next都是野指针，在此要为其置空，避免非法访问。
最后这个接口要把创建的节点的指针作为返回值，来供外部接口找到位置插入。
代码如下：
// 创建结点. ListNode* ListCreate(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; }
尾插接口
在单链表中，如果我们需要尾插，就需要先找尾，但是我们观察一下双链表的结构：
可以看到，由于双链表循环的特性，其哨兵位的prev指针，指向的就是最后一个节点。也就是说，我们无需繁琐地找尾了，只需要使用pHead->prev就可以找到双链表的尾。
在找到尾后，我们就创建一个节点，来存放这个数值，即调用刚刚的创建节点接口。
创建好了节点，最后就是调整链表内部的指针指向。此处由于是尾插，我们就需要执行下列步骤来调整指针：
1.将新节点的next指向哨兵位
2.将哨兵位的prev指向新节点
3.将原先的尾节点的next指向新节点
4.将新节点的prev指向原先的尾节点
如图：
绿色为原指针，蓝色为被调整的指针，红色为调整后的指针
代码如下：
// 双链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* tail = pHead->prev; ListNode* newnode = ListCreate(x); //调整指针 newnode->next = pHead; pHead->prev = newnode; tail->next = newnode; newnode->prev = tail; }
头插接口
与尾插类似的，先创建一个节点，然后调整对应的指针即可：
1.将哨兵位的后一个节点的prev指向新节点
2.将新节点的next指向哨兵位的后一个节点
3.将新节点的prve指向哨兵位节点
4.将哨兵位节点的next指向新节点
如图：
代码如下:
// 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newnode = ListCreate(x); //调整指针 pHead->next->prev = newnode; newnode->next = pHead->next; newnode->prev = pHead; pHead->next = newnode; }
在此处要十分注意指针调整的顺序问题，在尾插过程中，我们使用了临时变量tail来承接尾部指针，顺序就不重要了。但是此处我们并没有创建临时变量，那么此时就只有哨兵的next指向节点1（不考虑逆向查找），如果我们先改变了哨兵位的next，再将哨兵位的next赋给新节点，此时新节点得到的就不是原先的节点1了，会导致新节点自己指向自己。
例如：
尾删接口
既然要尾删，首先就是找尾。我们再尾插时说过pHead->prev就是尾节点。
找到尾部节点后，不要急于删除，要先对尾节点的前一个节点与哨兵位的指针进行调整：
1.将倒数第二个节点的next指向头节点
2.将头节点的prev指向倒数第二个节点
只要进行这两步骤，即可将尾节点排除在外，构成一个新循环：
此处橙色的指针，并没有发生改变，我只是将其表示出来，此处红色的指针与橙色的指针形参了新的循环，而节点4已经脱离这个循环了。虽然保留了两个绿色的指针指向这个循环，但是在free节点4的时候，这两个指针会一并销毁，所以不必担心。
最后只要free掉节点4即可。
代码如下：
// 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->next != pHead); ListNode* tail = pHead->prev; tail->prev->next = pHead; pHead->prev = tail->prev; free(tail); tail = NULL; }
断言分析：
此处由于是一个删除接口，那就要保证有节点可以删除。在单链表中，判断有没有链表的条件是phead->next == NULL。而在双链表中，貌似没有任何一个指针是指向空的，那没有节点应该是什么情况？
一开始在初始化双链表时我们就分析过，当一个链表没有有效节点时，哨兵位就会实现自循环，prev与next都指向自己。在此我们只需要保证哨兵位的next不为自己即可，即pHead->next != pHead。
头删接口
头删与尾删极为相似，最后问题都落在了调整指针上，对于头删，调整指针的过程为：
1.将哨兵位的next指向节点1的下一个节点
2.将节点1的下一个节点的prev指向哨兵位
调整后如下：
调整完指针后，直接free掉节点1即可，但是此时哨兵位已经不指向节点1了，此接口就找不到节点1了，更无法free了。所以要用一个临时变量来保存住头节点的指针。
代码如下：
// 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead); assert(pHead->next != pHead); ListNode* first = pHead->next; pHead->next = first->next; first->next->prev = pHead; free(first); first = NULL; }
查找节点接口
想要查找某个节点，就需要遍历这个链表。由于要保留住pHead，防止链表找不到头，所以我们要创建一个临时变量cur来遍历链表：
当cur指向的节点不是目标值时，cur移动到下一个节点
当cur指向的节点为目标值，返回cur
那么cur的结束条件是什么？
一样的，由于循环的特性，双链表内部没有空指针，cur也就不可能为空指针。由于哨兵位没有存数值，我们不妨从哨兵位的下一个节点开始遍历，当cur走了一圈回来，遇到哨兵位时，就说明已经遍历了一遍链表，停止移动，即cur == pHead时。
代码如下：
// 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->next; while (cur != pHead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
在pos位置前插入的接口
在刚刚的查找接口中，用户可以得到某个目标节点的值，记为pos。当用户想在该节点前插入某个值，就使用这个接口。
由于双链表内不出现空指针，所以pos不能为空指针，这里要对pos断言。
既然要插入，那就要创造一个节点，所以先调用一次创造节点的接口，随后调整指针即可。
调整指针：
1.将pos前一个节点的next指向新节点
2.将新节点的prev指向pos前一个节点
3.将新节点的next指向pos节点
4.将pos节点的prev指向新节点
如图：
此时除去蓝色指针，绿色与红色指针构成了一个新循环。
代码如下
// 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = ListCreate(x); pos->prev->next = newnode; newnode->prev = pos->prev; newnode->next = pos; pos->prev = newnode; }
删除pos位置的接口
由于我们已经有了pos的位置，而pos节点内部又存着前一个与后一个节点。所以删除此节点只需要调整指针后，free掉pos即可。
指针调整：
1.将pos节点的前一个节点的next指向pos的后一个节点
2.将pos节点的后一个节点的prev指向pos的前一个节点
调整后如下：
代码如下：
// 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; }
对插入与删除节点的优化
pos的插入与删除可以对任意链表内部的任意位置插入删除，那是否可以利用pos来完成头插，尾插，头删，尾删？
当然是可以的，在利用pos接口优化这四个接口后，代码量会缩小非常多，我们一一分析：
尾插优化：
我们的插入是在pos节点前插入，也就是pos->prev的位置插入。
当我们利用pos来进行尾插时，就要考虑，谁的prev指向尾节点？
这是一个具有循环特性的双链表，那么哨兵位的prev就是尾节点了，所以我们只需要往pos的插入接口中传入哨兵位pHead的地址即可：ListInsert(pHead, x)简化后代码如下：
// 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListInsert(pHead, x); }
尾删优化：
我们实现的pos删除是删除pos本身，也就是说，我们要利用pos删除接口来删除尾节点，就要对接口传入尾节点：ListErase(pHead->prev)，简化后代码如下：
// 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->next != pHead); ListErase(pHead->prev); }
头插优化：
想要头插，也就是在哨兵位与节点1直接插入。也就是在节点1前面插入，那么谁的prev指向哨兵位？
那当然是节点1，节点1就是pHead->next。所以传参过程就是：ListInsert(pHead->next, x)，简化后代码如下：
// 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListInsert(pHead->next, x); }
头删优化：
头删，就是删除节点1，那么我们只要传入节点1的地址即可，即：ListErase(pHead->next)，优化后代码如下：
// 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead); assert(pHead->next != pHead); ListErase(pHead->next); }
代码展示
LT.h文件：
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 typedef int LTDataType; #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }ListNode; //初始化 ListNode* LTInt(); // 创建结点. ListNode* ListCreate(LTDataType x); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 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);
LT.c文件：
#include "LT.h" //初始化 ListNode* LTInt() { ListNode* pHead = (ListNode*)malloc(sizeof(ListNode)); pHead->next = pHead; pHead->prev = pHead; return pHead; } // 创建结点. ListNode* ListCreate(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; } // 双向链表销毁 void ListDestory(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->next; ListNode* next = NULL; while (cur != pHead) { next = cur->next; free(cur); cur = next; } pHead->prev = pHead; pHead->next = pHead; } // 双向链表打印 void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->next; printf("pHead <-> "); while(cur != pHead) { printf("%d <-> ", cur->data); cur = cur->next; } printf("pHead\n"); } // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); /*ListNode* tail = pHead->prev; ListNode* newnode = ListCreate(x); newnode->next = pHead; pHead->prev = newnode; tail->next = newnode; newnode->prev = tail;*/ ListInsert(pHead, x); } // 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->next != pHead); ListNode* tail = pHead->prev; //tail->prev->next = pHead; //pHead->prev = tail->prev; //free(tail); //tail = NULL; ListErase(tail); } // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); //ListNode* newnode = ListCreate(x); //pHead->next->prev = newnode; //newnode->next = pHead->next; //newnode->prev = pHead; //pHead->next = newnode; ListInsert(pHead->next, x); } // 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead); assert(pHead->next != pHead); ListNode* first = pHead->next; /*pHead->next = first->next; first->next->prev = pHead; free(first); first = NULL;*/ ListErase(first); } // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->next; while (cur != pHead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = ListCreate(x); pos->prev->next = newnode; newnode->prev = pos->prev; newnode->next = pos; pos->prev = newnode; } // 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; }
test.c文件：
#include "LT.h" int main() { ListNode* phead = LTInt(); ListPrint(phead); printf("尾插测试\n"); ListPushBack(phead, 0); ListPushBack(phead, 1); ListPushBack(phead, 2); ListPushBack(phead, 3); ListPushBack(phead, 4); ListPushBack(phead, 5); ListPushBack(phead, 6); ListPushBack(phead, 7); ListPushBack(phead, 8); ListPushBack(phead, 9); ListPrint(phead); printf("头插测试\n"); ListPushFront(phead, 10); ListPushFront(phead, 20); ListPushFront(phead, 30); ListPushFront(phead, 40); ListPushFront(phead, 50); ListPushFront(phead, 60); ListPrint(phead); printf("尾删测试\n"); ListPopBack(phead); ListPopBack(phead); ListPopBack(phead); ListPrint(phead); printf("头删测试\n"); ListPopFront(phead); ListPopFront(phead); ListPopFront(phead); ListPrint(phead); ListNode* pos = NULL; pos = ListFind(phead, 5); printf("在5前插入123\n"); ListInsert(pos, 123); ListPrint(phead); pos = ListFind(phead, 20); printf("在20前插入456\n"); ListInsert(pos, 456); ListPrint(phead); pos = ListFind(phead, 2); printf("在2前插入789\n"); ListInsert(pos, 789); ListPrint(phead); printf("删除789\n"); pos = ListFind(phead, 789); ListErase(pos); ListPrint(phead); printf("删除456\n"); pos = ListFind(phead, 456); ListErase(pos); ListPrint(phead); printf("删除123\n"); pos = ListFind(phead, 123); ListErase(pos); ListPrint(phead); return 0; }
