2.3.3 双链表

教材导航 · 第2章

原书定位

印刷页P35起,对应PDF第47页。下文为目视整理的知识提要;完整内容见原书对照。

结点增加 prior 与 next 两个指针,可直接访问前驱。已知结点的局部插入、删除为 O(1)O(1),按位或按值定位仍通常是 O(n)O(n)。

在 p 后插入 s,先保存 p 的原后继 q,再令 s->next=q; s->prior=p;,若 q 非空则 q->prior=s;,最后 p->next=s;。删除时将左右相邻结点互连再释放目标;线性双链表的首尾边界需单独检查。

图2.9 双链表示意

图2.9 双链表示意,原书P35。

图2.10 双链表插入结点

图2.10 双链表插入结点,原书P35。

图2.11 双链表删除结点

图2.11 双链表删除结点,原书P36。

对应练习

2.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P35,PDF第47页

原书对照,原书P36,PDF第48页