扫码获取更多资源

●双向链表

在单链表或循环链表的结点中，只有一个指示后继的指针域，因此，从某个结点出发只 能顺链往后寻找其他结点。如果要寻找结点的前驱，则需要从表头指针出发。即在单链表 或循环链表中，求后继的时间复杂度为0（1）,而求前驱的时间复杂度为O（n）。为了克服单 链表或循环链表这种单向性的缺点，可以利用双向链表。 在循环链表中，每个结点中除了一个存放后继的指针域外，再增加一个指向其前驱的指 针域,链表中有两条方向不同的链，这样形成的链式存储结构称为双向循环链表，简称双向 链表（Double Linked List）

双向链表的结点结构

双向链表的结点结构如图2-17所示。其中，data为数据域，存放元素的数据；prior为 前向指针域,存放其前驱的地址；next为后向指针域，存放其后继的地址。

双向链表的头结点和头指针

在双向链表的第一个结点之前也附加一个同结构的结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息；头结点的前向指针域 存储指向最后一个结点的指针，后向指针域存储指向第一个结点的指针，如图2-18（a）所示。 指向头结点的指针是头指针。当头结点的前向指针域和后向指针域均指向头结点自己时, 称为空双向链表，如图2-18（b）所示。

双向链表的主要特点

顺链向后扫描寻找第I个结点，检查插入参数|是否合理，如果不合理，则给出相应信息 并退出运行；如果合理，则生成一个新结点，并将待插数据元素值赋给其数据域，然后按照 如下步骤完成插入：

（1） 设新结点前向指针指向p结点的前驱。 （2） 设新结点后向指针指向p结点。 （3） 修改p结点前驱的后向指针。 （4） 修改p结点的前向指针。图2-19给出了在双向链表中插入新结点时指针的变化状况。

联系我们：