知识卡片
链式访问需要沿路径前进
单向链表没有由索引直接算出目标节点地址的固定步长。取得第i项需要从已有起点沿Next走i步,按值搜索也要逐项比较直到命中或到尾。
如果维护了直接节点或端点指针,相关局部更新可以避开这段查找。比较数组与链表操作时,要统一是否已定位目标的前提,不能用数组完整查找对比链表已知节点改链接。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
访问链表的第 个节点需要循 环 轮,时间复杂度为 。 // === File: linked_list.go === /* 访问链表中索引为 index 的节点 */ func access(head *ListNode
参考来源
- 位置:《Hello 算法--Go版本》第04章《数组与链表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;spine 1,归一字符[21741,21851))
- 结论依据:实际access和findNode循环及成本对照支持已知位置与查找分开。
- 原始内容:访问链表的第 个节点需要循 环 轮,时间复杂度为 。 // === File: linked_list.go === /* 访问链表中索引为 index 的节点 */ func access(head *ListNode