文档文本内容
本节内容
单链表
插入和删除
王道考研/CSKAOYAN.COM知识总览
王道考研/CSKAOYAN.COM关于简化图示的说明
单链表
单链表
(带头结点)
(不带头结点)
L
头结点
L
a
1
a
1
a
2
LNode * p = (LNode *) malloc(sizeof(LNode));
a
2
a
free(p); 4
NULL
a
4
a
NULL
3
a
3 p
L 头 a a a a NULL
1 2 3 4
内存 p 内存
王道考研/CSKAOYAN.COM按位序插入(带头结点)
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
找到第 i-1 个结点,
将新结点插入其后
头结点可以看作
“第0个”结点
L 头 a a a a NULL
1 2 3 4
p
e
s
malloc
王道考研/CSKAOYAN.COM按位序插入(带头结点)
分析:
①如果 i = 1(插在表头)
i-1=0
L 头 a a a a NULL
1 2 3 4
p
O(1)
e 最好时间复杂度:
s
注意:绿绿和黄黄顺序不能颠倒鸭!
王道考研/CSKAOYAN.COM按位序插入(带头结点)
分析:
①如果 i = 1(插在表头)
i-1=0
L 头 a a a a NULL
1 2 3 4
p
e
s
注意:绿绿和黄黄顺序不能颠倒鸭!
王道考研/CSKAOYAN.COM按位序插入(带头结点)
分析:
②如果 i = 3(插在表中)
i-1=2
L 头 a a a a NULL
1 2 3 4
p
e
s
王道考研/CSKAOYAN.COM按位序插入(带头结点)
分析:
③如果 i = 5(插在表尾)
i-1=4
L 头 a a a a NULL
1 2 3 4
p
e
s
O(n)
最坏时间复杂度:
王道考研/CSKAOYAN.COM按位序插入(带头结点)
分析:
④如果 i = 6(i>Lengh)
i-1=5
L 头 a a a a NULL
1 2 3 4
p
王道考研/CSKAOYAN.COM按位序插入(带头结点)
O(n)
平均时间复杂度:
王道考研/CSKAOYAN.COM按位序插入(不带头结点)
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
找到第 i-1 个结点,
将新结点插入其后
不存在 “第0个”
结点,因此 i=1 时
需要特殊处理
L a a a a NULL
1 2 3 4
p
e
s
malloc
王道考研/CSKAOYAN.COM按位序插入(不带头结点)
分析:
①如果 i = 1(插在表头)
如果不带头结点,则插
入、删除第1个元素时,
需要更改头指针L
L a a a a NULL
1 2 3 4
e
s
王道考研/CSKAOYAN.COM按位序插入(不带头结点)
分析:
②如果 i > 1…
L a a a a NULL
1 2 3 4
除非特别声
p
明,之后的代
后续逻辑和带
码默认带头结
头结点的一样
点
结论:不带头结点写代码更不方便,推荐用带头结点
注意:考试中带头、不带头都有可能考察,注意审题
王道考研/CSKAOYAN.COM指定结点的后插操作
某些情况下有可能分配
失败(如内存不足)
神秘未知区域…… x y ……神秘可知区域
O(1)
e
p 时间复杂度:
s
王道考研/CSKAOYAN.COM指定结点的后插操作
王道考研/CSKAOYAN.COM指定结点的前插操作
如何找到 p 结
点的前驱结点?
神秘未知区域…… x y ……神秘可知区域
p
传入头指针
高清无码
L 头 a a a a NULL
1 2 3 4
拒绝神秘
循环查找p的前驱
O(n)
时间复杂度: q,再对q后插 q p
王道考研/CSKAOYAN.COM指定结点的前插操作
O(1)
时间复杂度:
神秘未知区域…… xe y ……神秘可知区域
p
x
s
王道考研/CSKAOYAN.COM指定结点的前插操作
王道书版本
temp x
神秘未知区域…… x y ……神秘可知区域
p
e
s
王道考研/CSKAOYAN.COM按位序删除(带头结点)
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
找到第 i-1 个结点,将其
指针指向第i+1个结点,
并释放第i个结点
头结点可以看作
“第0个”结点
L 头 a a a a NULL
1 2 3 4
i=1
p
王道考研/CSKAOYAN.COM按位序删除(带头结点)
分析:
如果 i = 4… e
i-1=3
L 头 a a a aa NULL
1 2 3 44
p
q
O(n)
最坏、平均时间复杂度:
最好时间复杂度:O(1)
如果不带头结点,删除第1个
元素,是否需要特殊处理?
王道考研/CSKAOYAN.COM指定结点的删除
神秘未知区域…… x y ……神秘可知区域
p
删除结点p,需要修改其前驱
结点的 next 指针
方法1:传入头指针,循环寻找 p 的前驱结点
方法2:偷天换日(类似于结点前插的实现)
王道考研/CSKAOYAN.COM指定结点的删除
可能是指向一个结点,
也可能是指向NULL
神秘未知区域…… x yy ……神秘可知区域
O(1)
时间复杂度:
p q
王道考研/CSKAOYAN.COM指定结点的删除
单链表的局限性:
❌ 无法逆向检索,有
时候不太方便
如果p是最后
一个结点…
神秘未知区域…… x NULL
只能从表头开始依
次寻找p的前驱,
p q 时间复杂度 O(n)
王道考研/CSKAOYAN.COM知识回顾与重要考点
注意审题:带头否?
有坑:指定结点是最
后一个结点时,需要
特殊处理
Tips:
1. 这些代码都要会写,都重要
2. 打牢基础,慢慢加速
3. 体会带头结点、不带头结点的代码区别
4. 体会“封装”的好处
王道考研/CSKAOYAN.COM小功能模块化,
封装的好处
代码逻辑清晰
也可以称为“基本操作”。对
书本的概念理解不要教条化
指针p指向第 i-1个结点
p后插入新元素e
王道考研/CSKAOYAN.COM知识回顾与重要考点
注意审题:带头
否?
有坑:指定结点是最
后一个结点时,需要
特殊处理
Tips:
1. 这些代码都要会写,都重要
2. 打牢基础,慢慢加速
3. 体会带头结点、不带头结点的代码区别
4. 体会“封装”的好处
王道考研/CSKAOYAN.COM