知识卡片
链表以链接换取弹性位置
单链表在每个节点保存数据与后继引用,头引用给出入口,尾节点后继为空。节点不必连续,插入删除可通过修改链接完成,不必搬移后面全部元素。
代价是额外链接空间、分配管理与逐节点访问;按值找节点仍可能线性扫描,局部性也往往逊于连续数组。数量未知并不自动意味着链表更快,动态数组也能扩容,需按实际访问与修改方式选择。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 7.6 单链表
原书出处 · 1 处
- 7.6 单链表 · 查看原书依据
注意next是一个指针,它保存链表中下一个元素的地址。链表中的第一个元素是头部(head),最后一个元素是尾部(tail)。我们可以识别尾部,因为next不能是另一个链表元素的值,通常是空(NULL)指针。 图7-10所示的链表与数组之间的一个很大区别是,所有数组元素在内存中都是
参考来源
- 位置:《计算机系统解密》7.6 单链表(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0073.html)
- 结论依据:原文正文与本项全部图表实际读取;按具体表示、操作及适用条件解释,不把示例概括为所有语言或平台。
- 原始内容:注意next是一个指针,它保存链表中下一个元素的地址。链表中的第一个元素是头部(head),最后一个元素是尾部(tail)。我们可以识别尾部,因为next不能是另一个链表元素的值,通常是空(NULL)指针。 图7-10所示的链表与数组之间的一个很大区别是,所有数组元素在内存中都是