前言：Hello！大家好，我是@每天都要敲代码；上一期我们已经学习了无头单向非循环链表，没有掌握的朋友可以先去学这个无头单向非循环链表。今天我们就要开始学习新的内容了，有头双向循环链表，从名字我们也能看出来这两个链表是8种链表中的两个极端，一个是结构简单，一个是结构复杂；只要我们这两个掌握了，其它的也就不再话下来了！

目录

概念和结构：

带头双向循环链表： 

1.创建双链表：ListNode

 2.初始化：ListNodeInit

动态创建地址：CreatListNode

3.打印：ListNodePrint 

4.尾插：ListNodePushBack

5.头插：ListNodePushFront

6.尾删：ListNodePopBack

7.头删：ListNodePopFront

8.修改：ListNodeModify

查找：ListNodeFind

9.任意插入：ListNodeInsert

10.任意删除：ListNodeErase

11.计算大小：ListNodeSize

12.销毁：ListNodeDestory

13.代码复用：ListNodeInsert和ListNodeErase

14.所有具体代码：

---

概念和结构：

概念：

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而更简单了。

解析：

带头：带头说明是有一个头结点，也就是哨兵位；每次的插入和删除并不影响这个哨兵位(单链表是影响的)，并且这个头节点不存放任何的有效数据！

双向：双向说明每个节点都有两个指针；一个指向前驱的指针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记住它的下一位置first = phead->next；再进行链接：

逻辑图：

通过图形我们开始链接：

第一种方法：首先记住头指针的下一个，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

具体代码实现：

逻辑测试：

 尾删一个数据进行打印测试：

逻辑测试没问题 

8.修改：ListNodeModify

查找：ListNodeFind

对于修改和单链表一样需要先去查找，根据给出的数据返回的地址进行修改：

查找具体代码：

修改具体代码： 

主函数里面的调用情况： 

  

逻辑测试： 

我们不妨就把数据1修改为数据100：

测试逻辑没问题 

9.任意插入：ListNodeInsert

     还记得对于单链表是怎样插入的吗？传了几个参数？当时我们传了3个参数：phead、pos、x；而对于双链表我们只需要传2个参数：pos、x；为什么呢？因为单链表传头结点是为了找到pos的前一个指针，我们只能通过遍历的方式；但是对于双链表我们pos->prev就直接找到上一个结点了！是不是更加的方便！！！

逻辑图：

    我们首先要记住pos的前一个结点：prev = pos->prev，然后开始链接，prev->next = newnode，newnode->prev = prev，newnode->next = pos，pos->prev = newnode

具体代码：

逻辑测试：

在100前面插入1

逻辑测试没问题

10.任意删除：ListNodeErase

    对于删除我们只需要一个参数，就是pos的地址，然后还需要记录它的前一个位置prev和后一个位置next，最终释放pos，让pos置空。

逻辑图：

     根据上图进行链接，首先记住pos的前一个位置和后一个位置：prev = pos->prev，next = pos->next ；然后prev->next = next，next->prev = prev，free(pos)，pos = NULL

具体代码：

 

 逻辑测试：

删除数据100进行打印测试

逻辑测试没问题 

11.计算大小：ListNodeSize

     对于计算大小很简单，我们定义一个计数器count就可以了；只需要注意一点，我们是从第二个数据开始计算数据的大小，对于头节点是不算的：

具体代码：

逻辑测试：

统计此时数据的个数

4个数据，计算的大小也是4，逻辑测试没问题

12.销毁：ListNodeDestory

      链表的销毁和顺序表不同，顺序表是连续的空间，free一次就可以；而链表创建的空间是不连续的，我们malloc多少次，就需要free多少次；并且我们最终也要把头指针(哨兵位)也要释放掉；下面看具体代码：

 具体代码：

13.代码复用：ListNodeInsert和ListNodeErase

     对于双链表虽然结构复杂，但是操作起来很简单；包括一些特殊情况：在单链表中空链表和一个节点的问题，在这里一个代码段就可以适合所有的结果；是不是很方便呢？那么我们在思考一个问题，能否用任意插入和任意删除去替代其它函数呢？

1.任意位置插入代替尾插：任意位置插，是在pos的前面插入，我们思考一下，在头指针的前面插入，不就相当于在尾插了吗？

具体代码如下：

测试结果也能得到我们的预期结果：

2.任意位置插入代替头插：

一直在头指针phead的next插入，不就相当于头插进行头插？

具体代码如下：

 测试结果也能得到我们的预期结果：

3.任意位置删除代替尾删

对于尾删，我们只需要传过去尾指针：phead->prev

具体代码如下：

 测试结果也能得到我们的预期结果：

 4.任意位置删除代替头删

对于尾删，我们只需要传过去尾指针：phead->next

具体代码如下：

测试结果也能得到我们的预期结果：

14.所有具体代码：

总结：

    还是那句话，对于链表的操作还是要动手画图！！！相对于单链表来说，双链表虽然结构复杂，但操作起来似乎更简单一点；无论是普通情况里面有很多元素，还是特殊情况空链表、一个节点的插入和删除；带头循环双链表都能用一段代码区解决；近乎完美。

    这里我们大概写了10个常用的函数接口，希望对各位有所帮助；感兴趣的同学也可以写成项目工程的格式！！！

春天来了，一起分享一下校园图片吧！