2.3.6 顺序表和链表的比较
原书定位
印刷页P37起,对应PDF第49页。下文为目视整理的知识提要;完整内容见原书对照。
| 方面 | 顺序表 | 链表 |
|---|---|---|
| 按位访问 | 一般 | |
| 按值查找 | 无序 ;有序可折半 | 一般 |
| 插入、删除 | 常需移动元素 | 已知所需指针时局部修改 |
| 空间 | 连续、无每结点指针开销 | 分散、需要指针或游标 |
| 规模变化 | 容量与扩容需管理 | 可逐结点分配与释放 |
选择取决于主要操作、规模变化和环境。链表的局部修改快,不能省略定位过程;尾指针能加速尾插,却不能使单链表删除尾结点自动变为常数时间。
对应练习
关联知识
原书对照
展开原书对照截图

