一.双向链表结构
我们一般所说的双向链表是带头循环双向链表，这里的带头更我们之前的头节点不是一回事。带头链表里的头节点，实际上为哨兵位，哨兵位的头节点种是不存放任何有效数据的，只是站在这里起到放哨的作用。
哨兵位的意义：避免遍历数组时发生死循环。
虽然双向链表的结构比单链表更加复杂，但是实现其实更加简单。
二.双向链表的实现
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev; //指针保存前1个节点的地址
LTDataType data;
struct ListNode* next; //指针保存下1个节点的地址
}LTNode;在双向链表中，我们需要两个指针一个指向前一个节点，另一个指向下一个节点。这里我们还是以存储整形数据为例。
在链表中，我们存储新的数据是要创造节点的，所以为了方便，我们单独封装一个函数来实现这个功能。
然后就是链表的初始化。
void ListNodeInit(struct ListNode** pphead);为什么这里要使用二级指针呢？
phead是指向哨兵位的指针，因为链表开始为空，所以phead指向空，pphead是指向pphead的指针，我们为了让phead指向哨兵位，需要改变phead的值，为了改变一级指针的值，我们就需要使用二级指针。
void ListNodeInit(struct ListNode** pphead){
*pphead = LTNBuyNode(-1);
};我们直接使用我们前面写的创造节点函数就行，这也是为什么我们在创造节点函数中，要让节点自己指向自己的原因。
在我们创建完了双链表后，如何打印数据呢？
void LTNPrint(LTNode* phead);void LTNPrint(LTNode* phead){
assert(phead);
LTNode*pcur = phead->next;
while(pcur != phead){
printf("%d->",pcur->data);
pcur = pcur->next;
}
printf("\n");
};在双向链表中，我们知道第一个节点哨兵位是不存放有效数据的，所以我们pcur起始位置就应该是第二个节点,为了避免死循环，当pcur遇到phead的时候就应该停止打印了.
这里与单链表很像，单链表是遇到空停止。
尾插函数：
void ListNodepushback(LTNode* phead, LTDataType x);在双链表中，尾插数据很简单，我们知道哨兵位的前一个节点就是尾结点，所以不需要遍历数组找到尾结点了。
尾结点有一个特点就是，它的next指针指向哨兵位，它的prev指针是指向倒数第二个节点。
如何插入数据呢？
首先我们先创建一个新的节点。
我们先不改变原本的链表，我们先来改变新的节点，这个节点要称为新的尾结点，那么它的next指针要指向哨兵位，它的prev指针要指向原本的尾结点。
newnode->next = phead;
newnode->prev = phead->prev;然后我们在看原链表，我们需要将原本的尾结点的next指向新的尾结点，然后就是将哨兵位的prev指针指向新节点，此时我们就完成了尾插数据。
void ListNodepushback(LTNode* phead, LTDataType x) {
assert(phead);
LTNode*newnode = LTNBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;//1
phead->prev = newnode;//2
};思考一个问题1和2两行代码可不可以交换，如果不可以说明原因。
答案是不可以的。读者可以自行画图理解。这里简单说明一下
如果先执行2，我们就改变了phead的prev指针，这样我们就找不到原本的尾结点了，这样1就不对了。
头插函数：
void ListNodepushFront(LTNode* phead, LTDataType x);如何头插数据呢？
同理我们先创建新的节点。
assert(phead);
LTNode*newnode = LTNBuyNode(x);我们还是现在新的链表上进行更改，新节点作为哨兵位的下一个节点，它的next要指向原本的第二个节点，它的prev节点要指向哨兵位。
newnode->next = phead->next;
newnode->prev = phead;如何我们在改变原链表，原本链表的第二个节点的prev要指向新节点，然后让phead的next指向新节点这样就完成了插入。
phead->next->prev = newnode;//1
phead->next = newnode; //2同理思考一下这里的1和2可不可以互换位置？
答案是不可以，如果互换我们就找不到原本的第二个节点了。
尾删函数：
void ListNodepopback(LTNode* phead){
assert(phead);
assert(phead->next != phead);
LTNode* delnode = phead->prev;
delnode->prev->next = phead;
phead->prev = delnode->prev;
free(phead->prev);
delnode = NULL;
}为了方便我们使用，我们不能直接上来就释放要删除的节点，不然我们就无法找到倒数第二个节点了，所以我们先存储起来。
我们要让倒数第二个节点的next指向phead使其称为新的尾结点，然后再将phead的prev指针指向它，这样就完成了删除，最后释放掉delnode。
注：开头的断言多了一个，双链表中的节点个数至少要是一个，我们的哨兵位是不能删除的，所以我们要进行，断言以防止将哨兵位删掉了。
头删函数
void ListNodepopFront(LTNode* phead);头删就是删除哨兵位的下一个节点，所以为了防止删除哨兵位，所以我们也要断言一下。
void ListNodepopFront(LTNode* phead) {
assert(phead);
assert(phead->next != phead);
LTNode* delnode = phead->next;
delnode->next->prev = phead;
phead->next = delnode->next;
free(phead->prev);
delnode = NULL;
}接下来就是指定位置插入数据的函数了。
但是在我们删除数据之前我们需要先找到这个位置才行，所以我们要完成查找函数。
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while(pcur != phead){
if(pcur->data == x){
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
查找到时就返回这个节点的地址，否则就返回空。
//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {
if(pos)
ListNodepushFront(pos,x);
};
//在pos之前插入数据
void LTInsertbefore(LTNode* pos, LTDataType x) {
if (pos)
ListNodepushback(pos,x);
};通过前面的头插尾插函数，我们不难发现头插起始就是在哨兵位的后面插入一个数据
尾插就是在哨兵位值前插入一个数据，
所以我们可以直接使用这两个函数，将pos当作哨兵位。
void LTErase(LTNode* pos) {
if (pos)
ListNodepopFront(pos->prev);
};头删是删除哨兵位之后的节点，那么我们要删除pos位置上的数据，起始就是将pos->prev当作头节点删除其后位置的数据就行。
销毁双链表
void LTDestory(LTNode* phead) {
assert(phead);
LTNode* pcur = phead->next;
LTNode* next = pcur->next;
while (pcur != phead) {
free(pcur);
pcur = next;
next = next->next;
}
free(phead);
phead = NULL;
};销毁双链表，需要释放掉所以节点，为了防止释放后无法找到下一个节点，还需要一个指针来保存下一个节点。
