2.5　双向链表

2.5.1　双向链表

在前面介绍的单链表及循环链表中,每个结点中只有一个指示后继结点的指针域,因此,从任何一个结点都可以通过指针域找到它的后继结点。但如果需要找出该节点的前驱结点,此时需要从表头结点出发重新查找。换句话说,在单链表中,如果要查找某结点的后继结点,则执行时间为O（1）,而查找其前驱结点的执行时间为O（n）。

为了克服单向链表的这种访问方式的单向性,可以构造双向链表。在双向链表中,每一个结点除了数据域外,还包含两个指针域,一个指针（next）指向该结点的后继结点,另一个指针（prior）指向它的前驱结点。双向链表的结点结构如图2－13所示。

图2－13　双向链表的结点结构

双向链表的结构可定义如下。

与单链表相比,双向链表具有更加灵活的优点。从双向链表中的任何一个结点出发,既可以顺着后继指针链向后查找,又可以顺着前驱指针链向前查找。当然,这是以增加存储空间为代价的。

双向链表也有多种形式。例如,可以带头结点,也可以不带头结点；可以是循环的,也可以是非循环的；可以是静态的,也可以是动态的等。如图2－14所示的是带头结点的双向循环链表,其中head为头指针。

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

由于在双向链表中既有前向链又有后向链,因此,寻找任一结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中的某一结点,则有下式成立。

p->prior->next=p=p->next->prior

2.5.2　双向链表的操作

1.双向链表的插入操作

在双向链表上进行插入操作时,需要同时修改两个方向上的指针。假若采用动态存储结构,prior和next分别表示结点的前驱指针和后继指针,则在p结点前插入新结点q的过程如图2－15所示。

图2－15　在p结点前插入新结点q

其中,有下列等式成立。

2.双向链表的删除操作

在双向链表上进行删除操作,删除p结点的过程如图2－16所示。

图2－16　删除p结点

其中,有下列等式成立。

p->prior->next=p->next;

p->next->prior=p->prior;

2.5.3　静态链表

在程序中,链表还可以用数组来描述,具体如下。

由于数组变量属于静态变量,因此,将这种链表称为静态链表。

【例2－5】　线性表（a,b,c,d）可按如图2－17所示的形式存放。这是一个不带表头结点的单链表。

图2－17　静态单链表的存储结构

在这种表示方法中,链表中的一个结点对应数组中的一个数组元素。如果某结点在数组中的下标为i,则s[i].data和s[i].next分别为该结点的数值字段和后继结点指针字段；如果后继指针字段为0,则表示该结点无后继结点。

为了在静态链表上实现插入和删除操作,可将数组中那些未使用的元素通过next字段构成一个备用单元链表（为了避免混淆,将原先那个链表称为数据链表）。每当需要往数据链表中插入结点时,就取备用单元链表中的第一个结点作为数据链表中新插入结点的存储空间；每当从数据链表中删除一个结点时,就把这个被删除结点链接到备用单元链表上。

【例2－6】　有一个线性表（a,b,c,d）,若要对这个线性表进行插入和删除操作,线性表的长度不超过10,故可用一维数组s表示数据链表和备用单元链表,如图2－18所示。其中,head是数据链表的表头指针,avail是备用单元链表的表头指针。

图2－18　数据链表和备用单元链表

此时,若要插入新结点x,使线性表（a,b,c,d）变为线性表（a,b,x,c,d）,可将备用单元链表中的第一个结点s[10]作为数据链表中新插入结点的存储空间,将x存入s[10].data中,并将s[10].next、s[1].next、avail的值分别改为4、10、9,其结构如图2－19所示。

如果要删除一个结点,使线性表由（a,b,x,c,d）变为线性表（a,b,x,d）,则只需将s[10].next、s[4].next、avail的值分别改为7、9、4,其结构如图2－20所示。

图2－19　在数据链表中插入新结点

图2－20　从数据链表中删除一个结点

2.5.4　顺序表和链表的比较

（1）在链表中的每个结点,除了数据域外,还需要额外设置指针（或光标）域,当每个结点的数据域所占字节不多时,指针域所占存储空间的比重就会更大。

（2）在链表中的任何位置上进行插入和删除操作时,都只需要修改指针。而在顺序表中进行插入和删除操作时,平均要移动表中近一半的结点,尤其是当每个结点的信息量较大时,移动结点的时间开销就相当大了。因此,对于频繁进行插入和删除的线性表,宜采用链表做存储结构；若表的插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表；而若是按序号存取,则宜采用顺序表。