知识卡片

普通读书笔记卡 · 5654.d.1.b.1

链表插入先接后继再接前驱

理解等级:中级

已知前驱节点n0和待插入节点P时,先让P.Next保存原来的后继,再让n0.Next指向P,便把新节点插进链中。顺序保证原后继不会在改链接时丢失。

这里只改固定数量指针,前提是前驱已定位、非nil,P的加入不破坏原有结构。若还要从头查找前驱,总成本包含查找,不能只用常数改链接说明整个插入请求是常数时间。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      只需改变两个节点引用(指针)即可,时间复杂度为 。 相比之下,在数组中插入元素的时间复杂度为 ,在大数据量下的效率较低。 第4 章 数组与链表 hello‑algo.com 75 图4‑6 链表插入节点示例 // ===

    参考来源

    - 位置:《Hello 算法--Go版本》第04章《数组与链表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;spine 1,归一字符[21065,21175)) - 结论依据:实际insertNode n1/P.Next/n0.Next顺序及图4-6支持。 - 原始内容:只需改变两个节点引用(指针)即可,时间复杂度为 。 相比之下,在数组中插入元素的时间复杂度为 ,在大数据量下的效率较低。 第4 章 数组与链表 hello‑algo.com 75 图4‑6 链表插入节点示例 // ===