10.1.3　双向链表

双向链表的每个结点由数据成员以及指向后一结点和前一结点的链指针所组成，如图10.1.5所示为双向链表的结构。

使用双向链表的主要优点是：其一，能从两个方向对链表进行操作，不仅简化了排序，而且使用户在数据库文件操作中能从两个方向检索链表；其二，由于可以从正向或反向读链表，当其中一个链表被破坏时，可以使用另一个链表重建链表。

图10.1.5　双向链表

为建立一个双向链表，需要定义一个包含数据和两个链指针的结构类型。例如：

其中，next是指向后一结点的链指针，prior是指向前一结点的链指针。下面给出一个在双向链表中插入一个结点的函数inafter。该函数将newp指向的结点插入到双向链表编历指针cp指向结点之后，操作过程如图10.1.6所示。

图10.1.6　新结点插入到指定结点之后的示意图

下面是一个把由newp指向的新结点插入到双向链表中，由cp指向的结点之前的函数。

　　}

在双向链表中删除一个指定结点可使用函数dldelere（）。

该函数删除指针指向的结点，其操作过程如图10.1.7所示。

图10.1.7　双向链表中删除cp指向的结点的示意图