知识卡片

普通读书笔记卡 · 4545.g.8.z.1.d.1.c.2 · 生成模型:GPT-6

有序链表仍需维护插入位置

理解等级:高级

从有序链表删除节点不会改变其余节点的相对次序,但插入新值必须先找到符合顺序的位置。维护中间节点指针最多帮助部分输入的搜索,不能自动把单链查找变成对数时间。是否选链表,应结合定位成本、访问模式和其他结构比较;“频繁删除必然胜过树或哈希表”没有通用保证。

这张卡片看不懂?

已有反馈 · 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)。 - 结论依据:原文比较有序插入删除并建议中间指针;限定其效果。 - 原始内容:链表不仅可以对数据排序,还可以在插入和删除元素之后保持数据的有序性。从有序链表中删除一个节点的操作与无序链表中相同,而向有序链表中插入新的节点则与无序链表中不同,为了保持链表的有序性,必须将新节点放到正确的位置。实际上,这意味着如果你有大量数据并且会频繁删除数据,那么相对于哈希表和二叉树,使用链表是