知识卡片
数据组织要权衡访问与维护
数据结构安排数据的存储和关系,算法利用这些关系完成处理。减少某项操作的成本,可能增加内存占用或另一项操作的成本,因此要按实际任务选结构。
链表在已经定位节点或前驱后能方便地改链接,但寻找目标仍可能线性;图保存更丰富关系,也需要额外空间。同一算法思路可用不同结构实现,效率必须连同操作条件一起比较。
数组的紧凑槽位减少指针开销,但可能预留未用容量或为扩容产生搬迁峰值;链表逐节点分配更灵活,却增加链接开销及分配管理。碎片化还依分配器和对象寿命,不能仅由“链表分散”无条件推断更严重。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
数据结构设计是一个充满权衡的过程 。如果想在某方面取得提升,往往需要在另一方面作出妥协。下面举两 个例子。 ‧ 链表相较于数组,在数据添加和删除操作上更加便捷,但牺牲了数据访问速度。 ‧ 图相较于链表,提供了更丰富的逻辑
- · 查看原书依据
在内存空间利用方面,数组和链表各自具有优势和局限性。 一方面,内存是有限的,且同一块内存不能被多个程序共享 ,因此我们希望数据结构能够尽可能高效地利用 空间。数组的元素紧密排列,不需要额外的空间来存储链表节点间的引用(指
参考来源
- 位置:《Hello 算法--Go版本》第01章《初识算法》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[15883,15993))
- 结论依据:原文目标/链表数组/图关系和结构算法互相依赖的实质比较合并,不沿用无条件链表插删快。
- 原始内容:数据结构设计是一个充满权衡的过程 。如果想在某方面取得提升,往往需要在另一方面作出妥协。下面举两 个例子。 ‧ 链表相较于数组,在数据添加和删除操作上更加便捷,但牺牲了数据访问速度。 ‧ 图相较于链表,提供了更丰富的逻辑
补充原书证据:spine 1 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;归一字符[29000,29110)。
- 结论依据:实际内存效率比较补充空间维度,避免阵列/链表性能绝对化。
- 原始内容:在内存空间利用方面,数组和链表各自具有优势和局限性。 一方面,内存是有限的,且同一块内存不能被多个程序共享 ,因此我们希望数据结构能够尽可能高效地利用 空间。数组的元素紧密排列,不需要额外的空间来存储链表节点间的引用(指