在前面两篇文章中，我们了解了单向链表和单项循环链表如下图：
此时，比如我已经获取到了C节点，那么我想要获取到C节点的前一个节点，就需要再次遍历该链表，且时间复杂度是O(n)。那么有没有一个好的方案可以便捷地获取到C的前一个节点呢，答案是使用双向链表。
双向链表的节点结构如下：
一般而言，单向链表、单向循环链表、双向链表、双向循环链表都会带有头节点，这样的话，设计起来就会比较方便。本篇文章中，我对双向链表和双向循环链表的讲解都是建立在链表有头结点的基础之上的。需要指出的是，我在上篇文章中，讲解单项循环链表的时候，是没有使用头结点的，但是之所以未使用头结点，就是为了给大家展示不使用头结点会是多么麻烦。
一、双向链表
1，双向链表的创建
逻辑如下:
1，新增一个双向链表节点，前驱后继均设为空，并将该新节点设置为链表的头结点
2，新建一个临时节点变量temp，来记录当前链表中的最后一个节点
3，循环添加节点，在每一个循环体中
（1）新增节点，并将其前驱后继设为空
（2）将新节点的前驱设为temp
（3）将temp的后继设为新节点
（4）将temp更新为新节点
代码如下：
2，双向链表的打印
思路如下：
自首元结点开始循环遍历，而不是自头结点开始打印。
当遍历到最后一个节点的时候跳出循环，通过后继是否为NULl来判断是否是最后一个节点。
代码如下：
3，向双向链表的指定位置上插入元素
逻辑如下：
1，新建节点，并将新节点的前驱后继均设置为NULL
2，遍历找到插入位置前面的那个节点，以下称为前驱节点
3，根据前驱节点找到后继节点
4，设置新节点的前驱为前驱节点
5，如果后继节点不为空，则设置后继节点的前驱为新节点
6，设置新节点的后继为后继节点
7，设置前驱节点的后继为新节点
代码如下：
4，删除双向链表指定位置上的节点
这里额外说明一下，我们之前讲了4种逻辑结构和2种物理结构，不管是集合结构、线性结构、树结构还是图结构，这些逻辑结构最终都是通过顺序结构或者链式结构这两种物理结构中的一种存储在内存中的。
逻辑如下：
1，找到该位置上的节点，如果节点不存在，则直接返回错误
2，分别使用三个变量来记录待删除位置的节点，以及其前驱结点和后继节点
3，判断后继节点是否存在，如果后继节点不存在，则直接将前驱节点的后继设置为NUll，然后free待删除节点
4，如果后继节点存在
（1）设置后继节点的前驱为前驱节点
（2）设置前驱结点的后继为后继节点
（3）free待删除节点
代码如下：
5，删除双向链表中指定的元素
逻辑如下：
1，找到该元素所在的节点，如果节点不存在，则直接返回错误
2，分别使用三个变量来记录待删除位置的节点，以及其前驱结点和后继节点
3，判断后继节点是否存在，如果后继节点不存在，则直接将前驱节点的后继设置为NUll，然后free待删除节点
4，如果后继节点存在
（1）设置后继节点的前驱为前驱节点
（2）设置前驱结点的后继为后继节点
（3）free待删除节点
代码如下：
6，在双向链表中查找元素的坐标
逻辑如下：
遍历循环，匹配给定的元素值；
如果没有找到，则返回-1
代码如下：
7，在双向链表中更新节点
代码如下：
二、双向循环链表
我们这里的双向循环链表是有头结点的，这样的话，进行增删改查的操作就都很方便。
双向链表：头结点的前驱为NUll，尾结点的后继为Null。
双向循环链表：头结点的前驱是尾结点，尾结点的后继是头结点。
以上是二者的唯一区别。
1，双向循环链表的初始化
逻辑如下：
1，创建一个节点，并将该节点的前驱和后继均设置为其自身
2，将新节点设置为链表的头结点
3，使用一个临时变量来记录当前链表中的最后一个节点
4，循环往链表中新增节点
（1）新建一个节点
（2）将新节点的后继设置为头结点
（3）将头节点的前驱设置为新节点
（3）将新节点的前驱设置为临时节点变量（尾结点）
（4）将尾结点的后继设置为新节点
（5）更新临时变量的指向为新节点
代码如下：
2，遍历打印双向循环链表
代码如下：
3，往双向循环链表中插入元素
逻辑如下：
1，循环遍历找到插入位置的上一个元素，以下称之为前驱结点
2，如果没有找到，则返回错误
3，如果找到了，则根据前驱结点，找到后继节点
4，新建一个节点，并设置其值
5，设置新节点的前驱为前驱结点，后继为后继节点
6，设置前驱结点的后继为新节点，设置后继节点的前驱为新节点
代码如下：
4，删除双向循环链表中的指定节点
逻辑如下：
1，找到指定位置上的节点
2，如果没有找到，则报错
3，找到待删除节点的前驱和后继
4，将前驱结点的后继设置为后继节点，将后继节点的前驱设置为前驱结点
5，free待删除节点
代码如下：
以上。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/193019.html