之前，我们已经学习了单链表，在实现单链表的过程中，也发现了单链表的缺陷。
比如在尾插时，需要找到尾结点；尾删时，需要找到尾结点的前一个节点；在任意位置删除时需要找到该位置前一个节点等等等…这些都需要用时间复杂度为 O(N)的算法来处理。
所以我们说，单链表 ，也就是单向无头非循环链表，是一个有缺陷的结构 ，它有时会作为其他数据结构的 子结构 。
基于单链表的这些缺陷，带头双向循环链表，也就是我们说的 双向链表 就完美的解决了 单链表 的这些问题。
1. 双向链表的概念
我们首先分析一下 双向链表 ，双向链表实际上就是 带头双向循环链表 。
之前我们说过链表的几种结构：带头 / 不带头，单向 / 双向，循环 / 非循环，而双向链表很明显就是这些结构中，最复杂结构 的集合。
它的主要表现就是，含有头结点 —— 有一个不存储有效数据的虚拟节点，链表永不为空，所以无需传二级指针，只需要改变节点之间的链接关系；双向 —— 可以通过一个节点直接找到上一个节点；循环 —— 链表头尾相连呈环状，链表中无空指针。
那么它的 结构 设计就必然有些特殊，由于是双向，所以要比 单链表 多一个 prev 用来找到上一个节点。同样的 单链表 有的 next、data 也必不可少；再考虑上它的循环结构，那么就需要最后一个节点的 next 能找到第一个节点，第一个节点的 prev 能找到最后一个节点。
我们可以大概画出它的 示意图：
从这幅图就可以看出，双向链表的结构十分完美，它完美解决了 单链表插入、删除数据时复杂的操作，加上存储单元之间的链接多样，让数据之间的管理变得非常简单！
那么它实现起来到底复不复杂呢，我们接下来就开始设计 双向链表 ，我们在实现的过程中感受！
2. 双向链表的实现
2.1 结构设计
双向链表 比 单链表 的结构多一个 prev 指针，用来记录上一个节点的地址。
typedef struct ListNode { LTDataType data; // 保存数据 struct ListNode* next; // 记录下一个节点的地址 struct ListNode* prev; // 记录上一个节点的地址 }LTNode;
2.2 接口总览
实现一个 双向链表 ，总共需要以下接口：
// 初始化 LTNode* ListInit(); // 使用返回值处理 // 打印 void ListPrint(LTNode* phead); // 尾插 void ListPushBack(LTNode* phead, LTDataType x); // 尾删 void ListPopBack(LTNode* phead); // 头插 void ListPushFront(LTNode* phead, LTDataType x); // 头删 void ListPopFront(LTNode* phead); // 查找元素 LTNode* ListFind(LTNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(LTNode* pos); // 销毁双向链表 void ListDestroy(LTNode* phead);
虽然接口和 单链表 差不多，但是这些接口的实现，远远比单链表 简单 地多~
而且这里有一个特殊的地方就是函数传参时，初始化接口参数 无参 ，其他接口传的是 一级指针 ，这是为什么？
首先需要明确的一点是，双向链表是带头的，含有一个头结点，就是我们单链表中提到的 哨兵位 。哨兵位不存储 有效数据 ，存在哨兵位链表就不为空，并使实现接口时更加方便。需要注意的是 只要存在哨兵位，链表的第一个节点就是哨兵位后面第一个节点 。
初始化函数 无参。双向链表初始化只需要创建哨兵位，然后得到哨兵位即可。在这里我也同样可以使用二级指针来操作，但是为了配合下面的接口函数，就不那么“突出”了~
其他接口参数传 一级指针，是因为我在进行相应的操作时，由于哨兵位不存储有效数据并且我并不需要改变哨兵位，所以我只需要找到哨兵位然后改变它的链接关系就可以，所以 不需要二级指针 。
2.3 初始化
创建一个 哨兵位 节点。
双向链表 在只有一个哨兵位时，让它自己指向自己。哨兵位的 next 指向它自己的prev ，哨兵位的 prev 指向它自己的 next 。说白了就是一个特殊的环形链表。
由于我们这里使用的是返回值的形式，所以只要创建返回就可以。
// 初始化 LTNode* ListInit() { LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); // 双向带头循环链表的prev指向next，next指向prev // 但是这里只有一个节点，所以只能让它自己指向自己 if (phead == NULL) { perror("ListInit"); exit(-1); } phead->next = phead; phead->prev = phead; return phead; }
2.4 创建新节点
当 双向链表 需要插入元素时，需要创建节点。这就很简单，直接 malloc 开辟，然后把值存入，两个指针给为空指针，然后返回节点就行。
// 创建新节点 LTNode* BuyListNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("ListPushBack"); exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
2.5 尾插
为什么说 双向链表 很完美，实现也比单链表 简单 ，从尾插就能看出来。
我们 单链表 的尾插，在链表为空时，需要特殊处理；在平常插入时，需要找到 尾结点 ，改变尾结点的链接。
对于 双向链表 的尾结点，就是哨兵位的 prev ，将其拷贝一份，放在 tail 中，然后将 tail 的 next 链接至新节点 newnode ，然后将 newnode 的 prev 链接到 tail。在处理一下 newnode 的 prev 和 tail 的链接就可以了~ 且这些步骤没有先后顺序 ~
怎么样，单链表 要 O(N) 的时间复杂度的尾插，在这里只需要用 O(1) 就可以完成，是不是简单多了？
// 尾插 void ListPushBack(LTNode* phead, LTDataType x) { assert(phead);// 一定不为空-->有哨兵位 LTNode* tail = phead->prev;// 尾就是prev，由于是双向循环链表，所以头的prev就是尾 LTNode* newnode = BuyListNode(x); // phead tail newnode tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
2.6 头插
对于 头插 来说，首先需要创建节点。
然后将哨兵位的后一个节点，即链表实际上的 第一个节点 phead->next，给定一个新节点 newnode 。然后将 newnode 的 prev 链接到 哨兵位。再将 newnode 的 next 给定为先前的第一个节点 next 。然后改变该节点 (next)的 prev 和 newnode 的链接关系。
// 头插 void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* next = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; }
2.7 尾删
对于 双向链表 的尾删，只要找到尾结点的前一个节点改变它和哨兵位的连接关系即可。
如果要找到尾结点的前一个节点，那么我只需要通过 哨兵位 的 prev 找到 尾，在通过 尾 的 prev 就可以找到 尾结点的前一个节点。然后调整这个节点和哨兵位的链接关系，然后 释放尾结点 就可以了。
但是要注意，当链表只有哨兵位的时候不能进行删除！！！
// 尾删 void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);// 防止把哨兵位删掉 LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; free(tail); phead->prev = tailprev; tailprev->next = phead; }
2.8 头删
对于头删来说，我需要删除链表的第一个节点，也就是 哨兵位的 next 节点 ，我需要改变 哨兵位 和 第二个节点 的链接关系，然后释放 第一个节点 。总体来说也很简单~
void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* next = phead->next; LTNode* nextNext = next->next; phead->next = nextNext; nextNext->prev = phead; free(next); }
2.9 查找
对于查找一个元素在 双向链表 中存不存在，那肯定是采用遍历链表的形式。
但是对于 双向链表 来说，它是没有指向 NULL 的节点的，它是一个环，停不下来。所以我们要把循环的截止条件设定为 != phead ，这个条件就表示，已经遍历过一遍链表了，走到哨兵位了。
如果找到，返回该节点的地址；如果找不到返回 NULL 。
// 查找 LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
2.10 在pos位置之前插入
在 pos 位置之前插入，那么通过 pos 的 prev 找到 pos 位置的上一个节点 posPrev ，然后改变 posPrev 和 新节点 newnode 之间的链接和 newnode 和 pos 之间的链接。和头插尾插思路大致相同。
// 在pos位置之前插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* posPrev = pos->prev; newnode->prev = posPrev; posPrev->next = newnode; newnode->next = pos; pos->prev = newnode; }
那么有了这个接口，那么我们就可以把它 复用 于 尾插 和 头插。
对于 尾插 来说， pos 位置就是 phead ，因为 phead 的前面就是链表的尾，在 phead 位置前插入，就是尾插：
void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead, x); }
对于 头插 来说，pos 位置就是 phead->next ，为第一个节点的前面，在 phead->next 位置前插入，就是头插：
void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); }
