2.11.7 双向链表 - c语言编程

2.11.7 双向链表

在单链表中，搜索一个指定节点的后继节点非常方便，只要该节点的link域的内容不为空，就可以通过link域找到该节点的后继节点地址。但是要搜索一个指定节点的前驱节点十分不容易，必须从链头开始，沿着link链顺序检测，直到某一节点的后继节点为该指定节点，则此节点即为该节点的前驱节点。为克服这一缺点，可以考虑双向链表。

在双向链表的每个节点中，应有两个链接指针作为它的数据成员：lLink指示它的前驱节点，rLink指示它的后继节点。因此双向链表的每个节点至少有3 个域：

节点之间的链接关系如图2.19所示。

（点击查看大图）图2.19 带表头的双向链表

指针 p 指向双向循环链表的某一节点，那么，p->lLink 指示p 所指节点的前驱节点，p->lLink->rLink中存放的是p所指前驱节点的后继节点的地址，即p所指节点本身。同样的，p->rLink 指示p 所指节点的后继节点，p->rLink->lLink 也指向p 节点本身。因此有p ==p->lLink->rLink == p->rLink->lLink，其过程如图2.20所示。

（点击查看大图）图2.20 节点指针的指向

双向链表的的插入、删除操作的思想与单向链表是一样的，但操作时稍复杂一些。如果要在当前指针current 所指节点后面插入一个新节点p，需修改5 个指针，把新节点链入两个方向的链中，具体操作如下：

p->lLink=current; p->rLink = current->rLink; 
/*改新节点的两个链域*/  
current->rLink=p; currentcurrent = 
current->rLink; /*改前驱节点的后继链域*/  
current->rLink->lLink=current; /*改后继节点的前驱链域*/

如果要删除双向链表中的一个节点，删除过程分两步，第一步先把当前节点从链中分离出来，修改前驱节点的后继指针和后继节点的前驱指针：

current->rLink->lLink=current->lLink; /*从lLink链中摘下*/  
current->lLink->rLink=current->rLink; /*从rLink链中摘下*/

第二步再把当前节点释放。