知识卡片
链表更新快于按键定位
双向链表已有目标节点指针时,插入或删除只需调整相邻指针,为 O(1);但按键查找最坏要逐节点扫描 Θ(n),所以“按键删除”连同定位仍为 Θ(n)。
数组恰好相反:随机下标访问快,保持相对次序的首部更新需搬移 Θ(n) 元素。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第10章 基本数据结构 · 查看原书依据
LIST-DELETE runs in O(1) time, but to delete an element with a given key, the call to LIST-SEARCH makes the worst-case running time be Θ(n).
参考来源
- 位置:《算法导论(第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 ).