2.3.6 顺序表和链表的比较

教材导航 · 第2章

原书定位

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

方面顺序表链表
按位访问O(1)O(1)一般 O(n)O(n)
按值查找无序 O(n)O(n);有序可折半一般 O(n)O(n)
插入、删除常需移动元素已知所需指针时局部修改 O(1)O(1)
空间连续、无每结点指针开销分散、需要指针或游标
规模变化容量与扩容需管理可逐结点分配与释放

选择取决于主要操作、规模变化和环境。链表的局部修改快,不能省略定位过程;尾指针能加速尾插,却不能使单链表删除尾结点自动变为常数时间。

对应练习

2.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P37,PDF第49页

原书对照,原书P38,PDF第50页