1.链表的分类
如图所示，链表具有以下不同特征，所以有2*2*2=8种不同的链表。
在上一篇文章中我们介绍的是单链表，Technically speaking,单向不带头不循环链表
这次我们就要来实现一下双向带头循环链表。
2.双向链表的具体实现
我实在是太懒了，还是跟前面单链表和顺序表一样要用两个.c文件，一个.h文件，不多说了。
双向链表的一个节点中包含三部分
1.存储的数据
2.指向下个节点的指针
3.指向前一个节点的指针。
用图表就是这样：
（1）初始化LTNode** pphead /LTNode* LTInit()
第一种方法显而易见，因为形参要对实参的改变做出影响，所以需要传地址。第二种方法呢，后面我们再介绍为什么要用。
初始化的时候需要创建一个新节点，也就是要动态开辟空间，这就涉及到了第二个函数
LTNode* LTBuyNode(LTDataType x)，
大体还是与之前单链表开辟空间大差不差，一样要判断空间是否开辟成功，然后将数据x存储在节点的data中，但这里，新开辟节点的两个指针都要指向本身，而不能置为NULL，因为我们要创建的是循环链表，如果置为NULL，就无法做到循环，而如果指向自己，则后面就可以通过插入数据实现循环效果
这就是新开辟出来的节点的效果，当然因为第一个开辟的节点是哨兵位，不存储任何有效数据。
在监视窗口中就可以清晰的看到，plist已经有一个哨兵位节点，next,prev指针均指向自己初始化步骤完成。
最后跟大家区分一个点，链表为空，代表链表中没有有效节点，也就是只有一个哨兵位节点，而链表无效证明连哨兵位都没有，这俩并不对等。
（2）尾插void LTPushBack(LTNode* phead, LTDataType x);
首先来画个图理解一下
先开辟一个newnode节点并调整newnode中两个指针的指向,确保原链表不受影响。
1.newnode此时的下个节点为哨兵位(newnode->next=head)
2.原来的尾节点d3的下一个节点调整为为newnode(newnode->prev=head->prev，其中head->prev表示原先的尾节点)
接下来调整剩下的两个指针
1.让原先尾节点d3指向下个节点的指针现在指向newnode(head->prev->next=newnode,其中head->prev表示原先的尾节点)
2.哨兵位的上一个节点要调整为newnode（head->prev=newnode）
尾插代码完成，进行测试前需要再写一个打印链表的函数
与单链表基本一致，断言链表有效且链表不为空，定义pcur指向哨兵位的下一个节点，也就是第一个有效节点，而循环则是在pcur遍历到哨兵位时结束。
打印结果：
尾插成功。
（3）头插void LTPushFront(LTNode* phead, LTDataType x);
头插并不是插在哨兵位之前，否则就与尾插相同了，头插是指插在哨兵位之后一个节点。
参考尾插，先改变newnode节点中的指针
1.newnode的下个节点调整为d1(newnode->next=head->next，head->next即d1)
2.newnode的前一个节点为哨兵位(newnode->prev=head)
然后再改变指向newnode的指针
1.哨兵位的下个节点为newnode(head->next=newnode)
2.d1的前一个节点为newnode(newnode->next->prev=newnode，此时newnode->next就是d1节点)
根据上述思路写出代码即可。
测试成功。
（4）尾删void LTPopBack(LTNode* phead);
还是先看图，为了方便理解，定义del指针指向双向链表的尾节点，防止后面要删除的节点丢失。
1.哨兵位上一个节点为尾节点的前一个节点(head->prev=del->prev)
2.尾节点的前一个节点此时指向哨兵位(del->prev->next=head,del->prev即为尾节点的前一个节点)
3.最后释放del指针指向的节点并手动置NULL
测试：
（5）头删void LTPopFront(LTNode* phead);
其实还是改变几个指针的指向，断言链表有效且链表不为空。
1.修改哨兵位的下一个节点为d2，(head->next=del->next)
2.d2的前一个节点修改为哨兵位(del->next->prev=head，此时del->next为d2)
测试：
（6）查找LTNode*LTFind(LTNodephead,LTDataType x);
不过多赘述，断言+遍历即可实现，若找到则返回指向节点的指针，若未找到则返回NULL。
（7）插入void LTInsert(LTNode* pos, LTDataType x);
利用查找时返回的下标(pos)实现这个功能，还是一步步梳理改变的指针指向，如图
先改变插入的节点newnode中的两个指针的指向：
1.newnode的下一个节点是原先pos的下一个节点d3(newnode->next=pos->next)
2.newnode的前一个节点是pos(newnode->prev=pos)
再改变指向newnode的两个指针(下面两行代码的顺序不能调换)：
1.d3的前一个节点要修改为newnode(pos->next->prev=newnode，这里pos->next即为d3)
2.pos的下一个节点是newnode(pos->next=newnode)
实现并测试完成。
（8）删除指定位置void LTErase(LTNode* pos);
处理与pos有关的四个指针：
1..d3指向上个节点的指针现在指向d1(pos->next->prev=pos->prev，pos->next即为d3)
2.d1中指向下个节点的指针现在要指向pos的下个节点d3(pos->prev->next=pos->next，pos->prev即为d1)
3.释放pos节点并置为NULL
（9）销毁void LTDestroy(LTNode* phead);
说到这里了，还记得前面初始化的时候提到的另一种方法吗？
LTNode* LTInit()，这种初始化与前面相比更好，因为能够更好的保持接口一致性。也就是传递的都是一级指针，就无需做区分。
因此我们可采用这种返回节点的初始化方式，更加清晰。
那么说回销毁，也是遍历然后释放节点即可。
不过这里有些巧妙的是，定义pcur遍历链表，但是在循环内定义了一个next指针，每次都指向pcur的下一个节点，而释放完pcur节点后，pcur会走到Next的位置，还是比较巧妙的。最后pcur走到哨兵位跳出循环，但是哨兵位还未被销毁，因此还要再销毁一次。
还没有结束！因为我们传的是一级指针，实参还要手动置为空
验证一下：
监视中显示此时数据都被销毁，而最后一步置空即可。
这就是双向链表实现的全过程，我发现不用遍历链表还是比较爽的。
又要爽爽写高数和线代了！
)
