双向链表
先赞后看好习惯 打字不容易，这都是很用心做的，希望得到支持你 大家的点赞和支持对于我来说是一种非常重要的动力 看完之后别忘记关注我哦！️️️
作者: @小小Programmer
这是我的主页：@小小Programmer
在食用这篇博客之前，博主在这里介绍一下其它高质量的编程学习栏目：
数据结构专栏：数据结构 这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏：算法 这里可以说是博主的刷题历程，里面总结了一些经典的力扣上的题目，和算法实现的总结，对考试和竞赛都是很有帮助的！
力扣刷题专栏：Leetcode想要冲击ACM、蓝桥杯或者大学生程序设计竞赛的伙伴，这里面都是博主的刷题记录，希望对你们有帮助！
看完本篇，相信你会对双向链表有一个比较深入的了解，而且会深深地体会到这一种链表相比于之前的单链表结构上的优越性、使用更为方便的特点。
一些链表的分类
在链表这一数据结构的模块里，我们可以通过它的结构，做出以下分类。
最常用的两种链表即：
1.无头单向非循环链表
这一种单链表，若单独使用，缺陷较多，不常用
1)因此，单链表经常在OJ题里面出现。
2)另外，它是很多复杂数据结构的子结构，如图、哈希表等
2.带头双向循环链表
1)常用。
2)STL里面的list就是这种链表
因此，这两种链表都是我们必须掌握的知识点
如果对无头单向非循环链表不太了解的伙伴，可以翻看我之前的博客，先做了解，再食用本篇【数据结构】单链表的介绍和基本操作（C语言实现）【保姆级别详细教学】
带头双向循环链表的基本结构
有了这些铺垫，我们就可以开始实现我们的双向链表了。
同样，实现这个链表需要3个源文件，这样可以使我们的程序可读性更高，更为清晰。对此不明白的伙伴可以翻看博主之前关于单链表或者扫雷游戏的作品，里面有讲解~
test.c：用于测试
List.c：用于实现接口
List.h：存放接口的声明
结点的定义、头指针的创建
然后在的里创建头指针
这个时候，我们还需要初始化一些我们的头结点，记住只有头结点链表为空。头结点初始化完之后，在后续操作中，头结点是不动的。
因此，我们现在需要创建一个头指针了！
此时需要一个开辟结点的接口，我们先写这个开辟结点的接口。
开辟结点接口
有了这个开辟结点的接口，我们可以初始化头结点了
初始化头结点接口
需要注意的点：
1.因为我们的头结点不存储数据，所以传0给开辟结点接口
2.只有头结点的时候链表为空，head的两个指针都要指向自己
接下来，我们可以先把打印接口写一写
打印接口
注意：
1.和单链表的遍历不一样，这里的遍历是到cur回到phead为结束标志，因为它是一个循环接口，这个很好理解
2.另外，与单链表不同，这里所有的接口都要assert()，因为头结点永远都在。
3.打印的时候要跳过头结点。
尾插接口
尾插：即在链表尾部插入一个新结点
尾插
首先，在单链表中，我们的第一步是遍历找尾，在这里我们需要这样吗？
phead的prev就是尾，根本就不用找。
因此，我们所需要做的，就是定义一个tail，让tail，phead，newnode之间的连接关系搞好，就大功告成了。
其次，在单链表中，我们重新调整结点之间连接关系的时候，常常需要临时指针储存我们的结点，为什么：怕丢，我们调整一个指针的时候，可能就会丢掉原来那个，为什么这么容易丢：因为每个结点只有一个指针指着。
而在这里，我们需要这样做吗？很明显不需要！我们每个结点都有多个指针指着，我们美美地调整连接关系就可以了。
其三：在单链表中，我们常常要在操作的时候分情况，链表为空吗，链表只有一个结点还是多个？在这里统统不需要，因为我们有带哨兵位的头结点。不明白的伙伴画个图就明白了。
我们直接上代码：
我们可以测试一下
尾删接口
尾删：在链表末尾删除一个结点
注意：删除结点的接口要多一个细节：判断链表是否为空，因此加多一句assert()即可。
头插接口
头插：在链表头插入一个新结点
写链表要细心，对特殊情况要敏感一些，考虑链表为空的情况。
我们用同样的逻辑套一下那个空链表的特殊情况，发现上面那段代码是符合的，first就是phead自己，完全没问题
这就是双向链表的优势
头删接口
头删：删除第一个结点
定义一个first指向第一个结点，second指向第二个结点，删除first，重新调整phead和second的关系即可。
同样：删除的接口要有
查找接口
查找接口通常和在任意位置插入结点，在任意位置删除结点，修改结点，这些功能结合在一起，因为我们找到以后，想改可以改，想插入可以插入，想删除可以删除了。
插入接口
删除接口
删除pos位置的结点
我们可以测试一下最后这三个接口
test.c
List.h
看到这里，相信伙伴们已经对带头双向循环链表已经有了比较深入的了解，掌握了基本的操作接口实现方法。相信我们已经深深感受到了这种结构的厉害之处。
如果看到这里的你感觉这篇博客对你有帮助，不要忘了收藏，点赞，转发，关注哦。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/1608.html