引言
数据结构之路在链表章节，前面介绍过单链表，今天我们来介绍最复杂的链表——双向链表（Double Linked List）
链表的分类
虽然有这么多的链表的结构，但是我们实际中 最常用 还是 两种结构 ： 单链表 和 双向带头循环链表
1. 无头单向非循环链表 ：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的 子结构 ，如 哈希桶、图的邻接表 等等。另外这种结构在 笔试面试 中出现很多。
2. 带头双向循环链表 ：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势， 实现 反而 简单 了，后面我们代码实现了就知道了。
前面我们讲的单链表，就是无头单向非循环链表，而现在讲的双向链表，就是带头双向循环链表。
双向链表的结构
注意： 这里的 “带头” 跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“哨兵位” ，哨兵位节点 不存储任何有效元素 ，只是站在这里“放哨的”
“哨兵位”存在的意义：
遍历循环链表避免死循环
双向链表的实现
定义
与单链表不同，一个节点里有两个指针，分别指向前节点和后节点，实现双向
创建新节点
创建新节点与单链表大致相同，抽离成函数方便创建节点
初始化
双向链表与单链表很大区别，就是在于初始化，创建哨兵位，而哨兵位不存储有效数据，所有这里存入-1，并让prev和next指针都指向自身
打印
首先assert断言，因为phead指向哨兵位，一定不为空，其次因为双向循环链表里没有NULL，所有停止条件就看哨兵位，当cur指针的下一个为哨兵位时，就代表走到尾部了
尾插
双向循环结构在空链表插入时，带来了极大的便利。因为prev指针的存在，使得找尾十分方便，不用遍历链表，直接访问哨兵位的上一个节点即可
如果是单链表，是不是还要讨论空链表的特殊情况啊？但是，在双向循环链表中，上述代码就可包含所有情况。因为哨兵位的存在，使得链表一定不为空。
同时，因为哨兵位的存在，我们不用传二级指针了，只用对结构体进行操作。怎么样，有没有发现双向链表的巨大优势？
运行结果
头插
头插时，要注意的就是要先链接后一个节点，再链接前一个节点
运行结果
判断链表是否为空
删除值得注意的是，不能删除哨兵位，要不然后续都无法对链表进行操作，所以专门写个函数来判断除了哨兵位链表是否为空，再用assert断言返回值
如果phead和phead->next相等，则为空，返回1，即为真 ；不相等，则不为空，返回0，即为假
尾删
经历过单链表，双向链表的尾删就显得太简单了。找尾tail直接往phead的上一位，同时创建tailPrev，在释放尾部节点后，双向链接哨兵位
运行结果
头删
同样，双向链表的头删也很简单。 找头first往phead的下一位，再创建second，在释放头部空间后，双向链接哨兵位
运行结果
