知识卡片
双向链表维护双向一致性
双向节点同时保存 Previous 与 Next,支持向前和向后访问。修改邻接关系时不能只修一边:插入中间节点要让它指向左右邻居,也让两侧邻居指回它;边界节点另行处理。可逆访问换来额外指针与维护责任,并不自动提高所有操作的速度。
保留链内任一有效节点时,可以沿Previous回到头部;若没有任何可达入口,双向结构也无法凭空恢复。每节点多一个链接带来空间和一致性维护成本。
结构图:
类图
classDiagram
class Node {
+Value int
+Previous *Node
+Next *Node
}
Node --> Node : Previous前驱
Node --> Node : Next后继
图中字段来自本章真实Go结构;箭头表示节点引用,不表示类型继承或额外线程安全保证。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- 05.6 Go 语言中的双向链表 · 查看原书依据
双向链表中的每个节点都既有指向前一个元素的指针,又有指向下一个元素的指针。
- 05.6.2 双向链表的优点 · 查看原书依据
可以重新找回它。然而,这种多功能性的代价就是每个节点需要维护两个指针。开发者需要考虑这种额外的复杂性是否值得。
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.6 Go 语言中的双向链表,spine091(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.6.html)。
- 结论依据:原文强调新节点与左右节点三个位置的指针修改。
- 原始内容:双向链表中的每个节点都既有指向前一个元素的指针,又有指向下一个元素的指针。
- 补充位置:spine093《05.6.2 双向链表的优点》;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.6.2.html。
- 补充原始内容:可以重新找回它。然而,这种多功能性的代价就是每个节点需要维护两个指针。开发者需要考虑这种额外的复杂性是否值得。