知识卡片

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

链式访问需要沿路径前进

理解等级:中级

单向链表没有由索引直接算出目标节点地址的固定步长。取得第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