前言：Hello！大家好，我是@每天都要敲代码；上一期我们已经学习了无头单向非循环链表，没有掌握的朋友可以先去学这个无头单向非循环链表。今天我们就要开始学习新的内容了，有头双向循环链表，从名字我们也能看出来这两个链表是8种链表中的两个极端，一个是结构简单，一个是结构复杂；只要我们这两个掌握了，其它的也就不再话下来了！
概念和结构：
概念：
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而更简单了。
解析：
带头：带头说明是有一个头结点，也就是哨兵位；每次的插入和删除并不影响这个哨兵位(单链表是影响的)，并且这个头节点不存放任何的有效数据！
双向：双向说明每个节点都有两个指针；一个指向前驱的指针prev，一个指向后继的指针next
循环：循环是指我们像圆一样整个是连通的，尾指针的后继next不再像单链表那样指向NULL，而是指向头结点(哨兵节点)；头节点的前驱prev指向的是尾结点
结构：
带头双向循环链表：
1.创建双链表：ListNode
对于双链表的创建需要3个参数；首先创建一个data变量用来存放数据、一个prev指针指向上一个结点、一个next指针指向后面一个节点点；如下图所示：
2.初始化：ListNodeInit
大家还记得吗？对于无头单向非循环链表我们当时把头指针初始化为NULL：
那么 现在带头双向循环链表我们怎么初始化呢？既然是带头肯定是要给它分配一个地址喽；这就需要malloc动态开辟空间；我们不妨随意给个数据0，用这个数据去开辟一块地址，作为头结点的指针。对于单链表我们是通过传一级指针的地址，二级指针接收的形式，今天双链表我们就用另一种方法就是传一级指针，然后一级指针接收。我们不妨通过封装函数ListNodeInit的形式去初始化，在这之前先封装动态创建地址的函数CreatNodeList：
动态创建地址：CreatListNode
开始初始化，初始化为下面这种结构形式：
3.打印：ListNodePrint
我们不妨先把比较简单的打印函数ListNodePrint 写出来，也有利于下面我们插入数据后进行测试。首先，肯定是要从第二个数据开始打印，第一个是头指针不存放有效的数据；其次当指针往下走，再次遇到头指针phead就停止打印。具体代码如下：
4.尾插：ListNodePushBack
对于单链表，我们当时传的是地址的指针，为什么呢？因为刚开始头指针是为NULL；我们不论是尾插还是头插进来的数据，谁插进来，谁就是头结点；这就造成我们要改变原来的地址和数据，所以要传一级指针的地址。但是对于有头的我们这个头结点就相当于哨兵一样，是永远不变的，所以我们只需要传一级指针就可以！
怎么链接呢？ 我们发现对于双链表我们就不需要去像单链表那样去考虑空链表、或者1个节点的情况；因为它必然是有一个哨兵位的头结点！我们需要保证的就是头结点不为空，所以不妨assert断言一下。
逻辑图：
不妨在考虑一下只有头节点(哨兵位)的情况：
发现没有？无论是普通情况里面有很多节点，还是特殊情况，是空链表(或者1个节点)的情况，都是没问题的！我们第一步就是要先找到尾结点tail，不用在去像单链表那样遍历，只需：tail = phead->prev，就可以找到尾结点了 ，找到尾结点后就根据逻辑图进行链接：
tail->next = newnode，newnode->prev = tail，newnode->next = phead，phead->prev = newnode
具体代码：
逻辑测试：
我们不妨尾插几个数打印一下：
逻辑测试没问题
5.头插：ListNodePushFront
逻辑图：
通过图形我们开始链接：
第一种方法：首先记住头指针的下一个，first = phead->next；然后开始链接：
phead->next = newnode，newnode->prev = phead，newnode->next = first，first ->prev = newnode，这种方法我们可以按任意顺序链接！！！
具体代码：
逻辑测试：
头插0，进行打印验证：
逻辑测试没问题
第二种方法：我们不需要记住phead的下一个位置first，直接进行链接！但是链接的顺序是有顺序的，我们要先链接右边的，在链接左边的。为什么？因为先链接左边，势必会造成原来的链接断开重连，它的下一个位置就找不到了；所以必须先链接右边。
newnode->next = phead->next，phead->next->prev = newnode，
phead->next = newnode，newnode->prev = phead；必须先链接右边在链接左边
具体代码：
逻辑测试：
把第一种方法屏蔽，用第二种方法头插0，进行打印验证：
逻辑测试没问题
6.尾删：ListNodePopBack
对于尾删，其实很简单，我们只需找一个指针记住尾指针tail的前一个节点prev，需要注意的一点是我们不能把phead头结点删除了，头结点的删除是最后销毁才删除的；所以不妨直接断言一下：assert(phead->next != phead)，出现这种情况就说明只剩下一个头节点了
逻辑图：
先找尾结点tail和尾前一个节点prev：tail = phead->prev，prev = prev->prev，然后把prev和头结点phead进行链接后，释放tail结点就可以了：prev->next = phead，phead->prev = prev，free(tail)，tail = NULL
具体代码：
逻辑测试：
尾删一个数据进行打印测试：
逻辑测试没问题
7.头删：ListNodePopFront
对于头删也很简单，我们不妨把头删的结点指针定义为first，我们要想删除first，就需要记住它的前一个节点的指针也就是phead和后一个节点的指针second，同样我们也不能删除头结点，需要断言一下：assert(phead->next != phead)
逻辑图：
怎么删除呢？先找到first和second，first = phead->next，second = first->next；然后就可以把phead和second进行链接，最后释放first就可以了：phead->next = second，second->prev = phead，free(first)，first = NULL
具体代码实现：
逻辑测试：
尾删一个数据进行打印测试：
逻辑测试没问题
