知识卡片

普通读书笔记卡 · 5578

双链以反向链接支持摘除

理解等级:初级

双链节点保存前驱和后继。已经持有有效目标节点时,可让前驱next接后继、后继previous接前驱,省去从头寻找前驱;插入也要维护两边方向一致。

按值寻找目标仍可能需要遍历,头尾空邻居或哨兵也须处理。多一个指针增加链接成本,不代表包含任意大小data的整个节点恰好翻倍;并发修改还需要同步。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 7.10 双链表 · 查看原书依据

      双链表不仅包括指向下一个元素的链接,还包括指向上一个元素的链接,如图7-20所示。这使每个节点的成本增加了一倍,但在删除元素的情况中不需要遍历链表,所以这是一种对空间和时间的权衡。 图7-20 双链表 双链表的优点是可以在任何地方插入元素或删除元素,而不必花时

    参考来源

    - 位置:《计算机系统解密》7.10 双链表(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0077.html) - 结论依据:本项全部正文与图表实际读取,区分作者示例、推导与实现边界;纠错另有明确说明。 - 原始内容:双链表不仅包括指向下一个元素的链接,还包括指向上一个元素的链接,如图7-20所示。这使每个节点的成本增加了一倍,但在删除元素的情况中不需要遍历链表,所以这是一种对空间和时间的权衡。 图7-20 双链表 双链表的优点是可以在任何地方插入元素或删除元素,而不必花时