一、 前言

前面文章已经描述什么是单向链表及其基本的C语言实现，虽然单向链表能够很好的完成“一对一”的数据存储问题，但需要大量查找前节点时，会耗费大量时间，因此，单向链表适用于需要频繁插入和删除节点，而查找节点较少的场景，为了能够提高链表的查找效率，有必要引入双向链表。

二、 什么是双向链表

双向链表（Doubly Linked List）是一种链式数据结构，它与单向链表类似，但每个节点有两个指针，一个指向前一个节点，一个指向后一个节点，这样，我们可以在双向链表中双向遍历。双向链表可以用于需要在链表中进行双向遍历的场合，相对于单向链表的优点是，可以在O(1)时间内删除或插入节点。但是，相对于单向链表，双向链表需要更多的内存空间来存储指向前一个节点的指针。

三、 双向链表的构成

由一系列节点（Node）组成，每个节点包含三个部分，一是数据域（Data），用于存储数据，二是指针域（Pointer），用于指向下一个节点，三也是指针域（Pointer），用于指向上一个节点。

双向链表构成

四、 双向链表的C语言操作

1、优缺点

优点：

a) 双向链表可以双向遍历，即可以从前往后遍历，也可以从后往前遍历，这样可以更加方便地实现某些操作。

b) 在双向链表中，删除一个节点时，不需要遍历整个链表来查找该节点的前驱节点，只需要通过该节点的前驱节点和后继节点的指针来完成删除操作，这样可以提高删除操作的效率。

c) 双向链表可以支持双向循环遍历，即链表的头节点和尾节点可以相互连接，形成一个环形结构，这样可以更加方便地实现某些特殊的操作。

缺点：

a) 双向链表的每个节点需要额外的一个指针来指向前一个节点，这样会占用更多的内存空间。

b) 在双向链表中，插入和删除操作需要修改节点的前驱节点和后继节点的指针，这样会增加操作的复杂度和时间复杂度。

c) 双向链表的实现比单向链表要复杂一些，需要考虑前驱节点和后继节点的指针关系，容易出现指针错误和内存泄漏等问题。

2、链表声明

创建个结构体，有3个成员，一个是存储数据，另2个分别是指向下一个节点和上一个节点的指针变量。

双向链表声明

3、创建新的节点

采用函数包装，创建成功函数返回空地址。

创建新节点

4、打印创建的链表中的内容

采用遍历方式，将整个链表遍历一遍，然后打印

打印链表内容

5、链表的插入：尾插

将一个新的节点插入到链表的尾部，使其成为新的尾节点，步骤如下：

a) 创建一个新的节点，将要插入的元素存储在节点中。

b) 将新节点的 prev 指针指向当前链表的尾节点。

c) 如果当前链表为空，将头节点指向新节点。

d) 如果当前链表不为空，将尾节点的 next 指针指向新节点。

e) 将尾节点指向新节点。

双向链表的尾插

6、链表的插入：头插

将一个新的节点插入到链表的头部，使其成为新的头节点，步骤如下：

a) 如果链表为空，则将新节点设置为头节点，并返回

b) 创建一个新节点，将要插入的数据存储在该节点中

c) 将新节点的 next 指针指向原来的头节点

d) 将原来的头节点的 prev 指针指向新节点

e) 将新节点设为新的头节点。

双向链表的头插

7、链表的插入：中间指定位置插入

将一个新的节点插入到链表的指定位置，使其成为新的链表，步骤如下：

a) 创建一个新的节点，将要插入的数据存储在该节点中；

b) 找到要插入的位置的前一个节点，例如要在节点A和节点B之间插入一个新节点，那么就需要找到节点A；

c) 将新节点的next指针指向要插入位置的后一个节点，例如将新节点的next指针指向节点A的next；

d) 将要插入位置的前一个节点的next指针的prev指针指向新节点，例如将节点A的next指针的prev指针指向新节点。

e) 将要插入位置的前一个节点的next指针新节点，例如将节点A的next指针指向新节点。

f) 将新节点的prev指针指向要插入位置的前一个节点，例如将新节点的prev指针指向A节点。

双向链表的指定位置插

8、链表的删除：指定位置删除

双向链表指定位置删除可以分为以下几个步骤：

a) 首先需要判断链表是否为空，如果为空则无法进行删除操作，直接返回；

b) 判断要删除的节点是否是头节点，如果是头节点，则需要将头节点指向下一个节点，并将下一个节点的前驱指针置为空；

c) 如果要删除的节点不是头节点，则需要先找到要删除的节点。从头节点开始遍历链表，直到找到要删除的节点；

d) 找到要删除的节点后，需要将该节点的前驱节点的后继指针指向该节点的后继节点，将该节点的后继节点的前驱指针指向该节点的前驱节点；

e) 最后，释放要删除的节点的内存空间，完成删除操作。

双向链表指定位置删

9、链表的查找：查找指定节点位置的内容

在链表中查找一个元素(按值查找和按位置查找)，可以按照以下步骤（和单链表一样）：

a) 从链表的头节点开始，依次遍历每个节点，直到找到目标元素或到达链表的末尾。

b) 在遍历过程中，每次比较当前节点的数据元素与目标元素是否相等，如果相等则返回该节点的位置。

c) 如果遍历到链表的末尾仍未找到目标元素，则说明该元素不存在于链表中，返回空指针或错误信息。

双向链表的查找

10、主函数测试

最后，为了验证写的函数是否正确，用主函数测试验证，均无问题。

主函数测试片段1

主函数测试片段2

测试结果

11、思考练习题

问题：写出如下算法：创建一个链表，里面有10个任意整型的值，要求在链表中获得所有两个和为指定值SUM的节点对应值的组合；若不存在，则给出提示信息。（如SUM=11、链表节点值为1-10之间的10个值，则组合有1+10、2+9、3+8、4+7、5+6这么几个节点值组合）

思路：

a) 先用尾插法，插入10个任意整型值到新链表中；

b) 采用排序法(如冒泡法)将链表值进行从小到大排序；

c) 定义两个指针p和q，分别指向链表的头和尾；

d) 计算p和q指向的节点值之和sum，如果sum等于SUM，则直接输出，然后p=p->next, q=q->prev,即p后移，q前移；

e) 如果sum小于SUM，则将p向后移动一位，重新计算sum；

f) 如果sum大于SUM，则将q向前移动一位，重新计算sum；

g) 重复步骤c-f，直到p和q重合或p的下一个节点和q重合时退出循环。

大家可以按照思路先练习一遍，若是能跑通，这块知识点基本上已熟悉，明天我会在微头条上公布实现算法的程序。

最后，希望大家可以点点赞，关注下，后面会不定期更新C语言、python相关知识点，以及控制工程中很火的ADRC相关知识点[机智]