2.3.4　双链表

从单链表的结构特征可以看到：当给定一个结点p时，沿着指针方向去查找p的后继结点是容易的，若要访问p的前趋结点就比较困难，此时唯一的方法是从表头开始顺着链查找。因为，单链表只有一个指针域，它用来存放该结点后继结点的地址，而没有关于前趋结点的信息。又如，当从单链表中删除任意一个结点时，也会遇到类似的问题，因为从单链表中删除一个结点，需要修改该结点前趋结点的指针。因此，对于那些经常需要既向前又向后进行查询的问题，采用双向链表比较适宜。双向链表是线性表的另一种形式的链式存储结构。

双向链表中的每个结点有两个指针域。其中，一个存放它的直接前趋结点的地址，另一个存放它的直接后继结点的地址。因此，在双向链表中一个结点至少有3个域，即数据域（data）、左指针域（llink）和右指针域（rlink）。双向链表的结点结构如下：

双向链表数据类型的定义：

一个双向链表可以是非循环的，也可以是循环的。图2－19和图2－20分别展示了带有表头结点的双向链表和双向循环链表的一般形式。

图2－19 带表头结点的双向链表

图2－20 带表头结点的双向循环链表

在双向链表中，若p是指向表中任意一结点的指针，则有

这一等式非常直观地反映了双向链表结构的本质，即第i－1个结点的右指针和第i＋1个结点的左指针都指向第i个结点，因而可随意在其上向前或向后移动，使插入和删除工作都变得十分容易。这是付出存储空代价而带来的好处。

下面先介绍双向链表插入和删除运算的基本操作。

设指针p指着双向链表中的结点B，指针f指着将要插入的新结点x，x插在两个数据元素A和B之间，此时需要修改4个指针（如图2－21所示）：

图2－21在双向链表中插入x结点

（1）f－llink＝p－llink；

（2）f－rlink＝p；

（3）（p－llink）－rlink＝f；

（4）p－llink＝f；

请注意p所在的位置和上述4个语句的书写顺序。

掌握了双向链表的插入操作，双向链表的删除操作就不难理解了。从双向链表中删除p所指的结点，如图2－22所示，需修改两个指针：

（1）左结点的右指针：

（2）右结点的左指针：

图2－22 从双向链表中删除结点y

双向链表插入和删除算法与单链表相似，核心代码如下，在这里不再详细说明。

插入结点f：

删除结点p：

思考：若插入到p结点的后面位置，算法如何实现？若删除p结点后面的结点或是前面的结点，算法如何实现？