知识卡片
哨兵统一链表边界
循环双向链表可用一个不代表真实元素的哨兵节点替代 NIL:哨兵的 next 指向首节点、prev 指向尾节点,空表时两者都指回哨兵。
这样头尾插删共享同一套指针更新,无须逐一判断边界;代价是每条链表多一个节点。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 哨兵统一链表边界
原书出处 · 1 处
- 第10章 基本数据结构 · 查看原书依据
A sentinel is a dummy object that allows us to simplify boundary conditions.
参考来源
- 位置:《算法导论(第4版)》第 10 章 10.2 节(`OEBPS/chapter010.xhtml`,文本字符 [18000, 21500);图 10.5/Art_P371)。
- 结论依据:原文定义 sentinel 并展示空表及头尾插删时指针连接,亦指出额外空间成本。
- 原始内容:A sentinel is a dummy object that allows us to simplify boundary conditions.