2.6　双向链表

2.6.1　双向链表的存储结构

顾名思义，双向链表（double linked list）就是链表中的每个结点有两个指针域：一个指向直接前驱结点，另一个指向直接后继结点。双向链表的每个结点有data域、prior域和next域3个域。双向链表的结点结构如图2-25所示。

其中，data域为数据域，存放数据元素；prior域为前驱结点指针域，指向直接前驱结点；next域为后继结点指针域，指向直接后继结点。

与单链表类似，也可以为双向链表增加一个头结点，这样使某些操作更加方便。双向链表也有循环结构，称为双向循环链表（double circular linked list）。带头结点的双向循环链表如图2-26所示。双向循环链表为空的情况如图2-27所示，判断带头结点的双向循环链表为空的条件是head->prior==head或head->next==head。

图2-25　双向链表的结点结构

图2-26　带头结点的双向循环链表

图2-27　带头结点的空双向循环链表

在双向链表中，因为每个结点既有前驱结点的指针域，又有后继结点的指针域，所以查找结点非常方便。对于带头结点的双向链表中，如果链表为空，则有p=p->prior->next=p->next->prior。

双向链表的结点存储结构描述如下：