知识卡片
哨兵循环链表
书中的双向循环链表用一个头节点作为哨兵:初始化时它的next和prev都指向自己;有数据后,头节点的前驱指向尾节点、尾节点的后继指向头节点,首尾相连成环。这样空表、首节点、尾节点的插入和删除都走同一套指针改写规则,不必写特殊分支。很多容器代码的复杂度来自边界分支,哨兵用结构消除了它们。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《TypeScript图形渲染实战:基于WebGL的3D架构与实现》第2章《TypeScript封装和实现常用容器》(源文件:_epub-src/OEBPS/Text/chapter49.xhtml、_epub-src/OEBPS/Text/chapter50.xhtml)
- 结论依据:原文说明List<T>是双向循环链表,包含一个头节点(哨兵节点),初始化时其next和prev都指向自身;头节点的前驱指向尾节点、尾节点的后驱指向头节点,首尾相连。
- 原始内容:它包含了一个ListNode<T>的头节点(哨兵节点),该头节点在链表初始化时,其next和prev成员变量都指向自身……头节点h的前驱指针指向最后一个节点(尾节点),而最后一个节点(尾节点)的后驱指针next指向头节点h,从而首尾相连,形成一个闭环。