2.3.5 双向链表

在前面讨论过的单链表和循环链表中，每个结点的指针域只有一个，用来存放后继结点的指针，而没有关于前驱结点的信息。因此，从某个结点出发，只能顺着指针往后查找其他结点。若要查找结点的前驱，这需要从表头结点开始，顺着指针寻找，显然，使用单链表处理不够方便。同样，从单链表中删除一个结点也会遇到类似的问题。为了克服单链表的这种缺点，可以使用双向链表。

1.双向链表的存储结构

双向链表中，每个结点有两个指针域：一个指向直接前驱结点，另一个指向直接后继结点。双向链表的结点结构如图2.28所示。

在双向链表中，每个结点包括3个域：data域、prior域和next域。其中，data域为数据域，存放数据元素；prior域为前驱结点指针域，指向直接前驱结点；next域为后继结点指针域，指向直接后继结点。

双向链表也可分为带头结点和不带头结点两种，带头结点使某些操作更加方便。另外，双向链表也有循环结构，称为双向循环链表。带头结点的双向循环链表如图2.29所示。

双向循环链表为空的情况如图2.30所示，判断带头结点的双循环链表为空的条件是head->prior==head或head->next==head。

在双向链表中，每个结点既有前驱结点的指针域又有后继结点的指针域，因此查找结点非常方便。如果p是指向链表中某个结点的指针，则有p=p->prior->next=p->next->prior。

双向链表的结点类型描述如下：

2.双向链表的插入操作和删除操作

对于双向链表的有些操作，如求链表的长度、查找链表的第i个结点等，与单链表中的算法实现基本没什么差异。但是，对于双向循环链表的插入操作和删除操作，因为涉及的是前驱结点指针和后继结点指针，所以需要修改两个方向的指针。

（1）插入操作

插入操作就是要在双向循环链表的第i个位置插入一个元素值为e的结点。插入成功返回1，否则返回0。

【算法思想】首先找到第i个结点，用p指向该结点。再申请一个新结点，由s指向该结点，将e放入到数据域。然后开始修改p和s指向的结点的指针域：修改s的prior域，使其指向p的直接前驱结点，即s->prior=p->prior；将p的直接前驱结点的next域，使其指向s指向的结点，即p->prior->next=s；修改s的next域，使其指向p指向的结点，即s->next=p；修改p的prior域，使其指向s指向的结点，即p->prior=s。插入操作指针修改情况如图2.31所示。

插入操作算法实现如下。

（2）删除操作

删除操作就是将带头结点的双向循环链表中的第i个结点删除。删除成功返回1，否则返回0。

【算法思想】首先找到第i个结点，用p指向该结点。然后开始修改p指向的结点的直接前驱结点和直接后继结点的指针域，从而将p与链表断开。将p指向的结点与链表断开需要两步：

①修改p的直接前驱结点的next域，使其指向p的直接后继结点，即p->prior->next=p->next。

②修改p的直接后继结点的prior域，使其指向p的直接前驱结点，即p->next->prior=p->prior。

删除操作指针修改情况如图2.32所示。

删除操作算法实现如下。

插入操作和删除操作的时间耗费主要在查找结点上，两者的时间复杂度都为O（n）。

注意：双向链表的插入操作和删除操作需要修改结点的prior域和next域，因此要注意修改结点指针域的顺序。