知识卡片

普通读书笔记卡 · 3622.a

链表更新快于按键定位

理解等级:中级

双向链表已有目标节点指针时,插入或删除只需调整相邻指针,为 O(1);但按键查找最坏要逐节点扫描 Θ(n),所以“按键删除”连同定位仍为 Θ(n)。

数组恰好相反:随机下标访问快,保持相对次序的首部更新需搬移 Θ(n) 元素。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 10 章 10.2 节(`OEBPS/chapter010.xhtml`,文本字符 [15000, 18500);图 10.4/Art_P370)。 - 结论依据:原文分别给出 LIST-SEARCH、LIST-INSERT、LIST-DELETE 的成本,并强调删除接口接收对象指针。 - 原始内容:L IST -D ELETE runs in O (1) time, but to delete an element with a given key, the call to L IST -S EARCH makes the worst-case running time be Θ( n ).