2.3.2.3 单链表插入

教材导航 · 第2章

原书定位

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

已知前驱 p,把新结点 s 插到其后:

s->next = p->next;
p->next = s;

必须先保存原后继。按位插入先找第 i−1i-1 个结点,整体 O(n)O(n);已知前驱则 O(1)O(1)。只给当前结点时,可以后插再交换数据来实现逻辑前插,但会改变结点与数据的对应关系,应用前应确认题意允许。

图2.5 单链表插入的指针修改顺序

图2.5 单链表插入的指针修改顺序,原书P32。

对应练习

2.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P31,PDF第43页

原书对照,原书P32,PDF第44页