知识卡片
有序链表仍需维护插入位置
从有序链表删除节点不会改变其余节点的相对次序,但插入新值必须先找到符合顺序的位置。维护中间节点指针最多帮助部分输入的搜索,不能自动把单链查找变成对数时间。是否选链表,应结合定位成本、访问模式和其他结构比较;“频繁删除必然胜过树或哈希表”没有通用保证。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.5.2 链表的优点 · 查看原书依据
链表不仅可以对数据排序,还可以在插入和删除元素之后保持数据的有序性。从有序链表中删除一个节点的操作与无序链表中相同,而向有序链表中插入新的节点则与无序链表中不同,为了保持链表的有序性,必须将新节点放到正确的位置。实际上,这意味着如果你有大量数据并且会频繁删除数据,那么相对于哈希表和二叉树,使用链表是
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.5.2 链表的优点,spine090(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.5.2.html)。
- 结论依据:原文比较有序插入删除并建议中间指针;限定其效果。
- 原始内容:链表不仅可以对数据排序,还可以在插入和删除元素之后保持数据的有序性。从有序链表中删除一个节点的操作与无序链表中相同,而向有序链表中插入新的节点则与无序链表中不同,为了保持链表的有序性,必须将新节点放到正确的位置。实际上,这意味着如果你有大量数据并且会频繁删除数据,那么相对于哈希表和二叉树,使用链表是