知识卡片
双链以反向链接支持摘除
双链节点保存前驱和后继。已经持有有效目标节点时,可让前驱next接后继、后继previous接前驱,省去从头寻找前驱;插入也要维护两边方向一致。
按值寻找目标仍可能需要遍历,头尾空邻居或哨兵也须处理。多一个指针增加链接成本,不代表包含任意大小data的整个节点恰好翻倍;并发修改还需要同步。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 7.10 双链表
原书出处 · 1 处
- 7.10 双链表 · 查看原书依据
双链表不仅包括指向下一个元素的链接,还包括指向上一个元素的链接,如图7-20所示。这使每个节点的成本增加了一倍,但在删除元素的情况中不需要遍历链表,所以这是一种对空间和时间的权衡。 图7-20 双链表 双链表的优点是可以在任何地方插入元素或删除元素,而不必花时
参考来源
- 位置:《计算机系统解密》7.10 双链表(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0077.html)
- 结论依据:本项全部正文与图表实际读取,区分作者示例、推导与实现边界;纠错另有明确说明。
- 原始内容:双链表不仅包括指向下一个元素的链接,还包括指向上一个元素的链接,如图7-20所示。这使每个节点的成本增加了一倍,但在删除元素的情况中不需要遍历链表,所以这是一种对空间和时间的权衡。 图7-20 双链表 双链表的优点是可以在任何地方插入元素或删除元素,而不必花时