知识卡片
双链表节点删除只需断链无需搬移
Go 的 container/list 用双链表实现列表容器,每个节点只记录自身的值和与前后节点的连接关系,彼此之间在内存中并不连续存放。插入或删除一个节点只需要修改被操作节点前后邻居的连接指针(断链、接链),不需要像 [[连续容器删除的代价本质]] 那样搬移其余元素,代价与容器总长度无关。发散:这本质上是”连续存储换随机访问速度”与”离散存储换任意位置增删速度”这一权衡的具体体现——切片在索引访。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《Go语言从入门到进阶实战》第3章《容器:存储和组织数据的方式》(源文件:_epub-src/OEBPS/Text/00073.xhtml)
- 结论依据:原文在该章节围绕“Go的`container/list`用双链表实现列表容器,每个节点只记录自身的值和与前后节点的连接关系,彼此…”给出定义、示例或限制条件;摘录中的术语、代码片段或对比关系直接支撑本卡片的结论。
- 原始内容:换号码了,他需要通知A和C,将自己的号码移除。这个过程就是列表元素的删除操作,如图3-5所示。 图3-5 从双链表中删除一人的电话号码 在Go语言中,将列表使用container/list包来实现,内部的实现原理是双链表。列表能够高效地进行任意位置的元素插入和删除操作。