知识卡片
链表插入先接后继再接前驱
已知前驱节点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 链表插入节点示例 // ===