代码之家 › 专栏 › 技术社区 › dc.

树:链接列表与数组(效率)

theory linked-list performance tree arrays

5

dc. · 技术社区 · 16 年前

这是一个任务问题,我很难用词来回答。

“假设一棵树每个节点最多可以有k个子节点。设V为每个节点的平均子节点数。对于V的值,将子节点存储在链接列表中比存储在数组中更有效(就所用空间而言)?为什么?”

我相信我能回答“为什么?”用简单的英语来说或多或少——使用链接列表会更有效,因为在实际填充值时,您只为链接列表中的节点分配空间,而不是占用大量的空节点(即,如果平均值低于最大值,则数组中的空索引)。

因此,如果在最大值为200时平均有6个子节点,则在创建树时,数组将为每个节点的所有200个子节点创建空间,但链接列表将仅根据需要为节点分配空间。因此,对于链接列表,使用的空间大约为(?)平均值;对于数组,所用的间隔将是最大值。

…我不知道什么时候使用阵列更有效。这是个骗人的问题吗?在创建数组时,是否必须考虑到数组需要对节点总数进行限制这一事实?

5 回复 | 直到 16 年前

1

5

Sam Harwell 16 年前

对于许多常用语言,阵列将需要分配存储 K (数据的)存储器地址。一个单独链接的列表需要每个节点2个地址(data&next)。一个双链接列表需要每个节点3个地址。

让 n 是特定节点的实际子节点数一 :

数组使用 K 内存地址
单链表使用2 N号地址
双链接列表使用3 n 地址

价值 K 允许您确定2 n 或3 n 与简单地将地址存储在一个数组中相比,地址将平均为增益或损耗。

2

5

Konrad Rudolph 16 年前

…我不知道什么时候使用阵列更有效。这是个骗人的问题吗?

这不是一个技巧问题。想想记忆开销链接列表中的。如何实现链接列表(与数组相比)?

另外(尽管这超出了问题的范围!)空间消费并不是唯一的决定因素。缓存在现代CPU中扮演着重要的角色,将单个子节点存储在数组中而不是链接列表中可以显著提高缓存位置(从而显著提高树的性能)。

3

Nick Dandoulakis 16 年前

数组必须预先分配空间,但我们可以使用它们快速访问任何条目。
列表在创建新节点时分配内存,这并不理想,因为
CPU时间的内存分配成本。

提示:如果您愿意,您可以一次分配整个数组,但通常我们会分配,
比如说,4个条目,当我们需要更多的空间时,我们通过加倍大小来调整它的大小。

4

1

herzmeister 16 年前

我可以想象,在许多情况下,使用 LinkedList 如果一个使用的数据项仍然具有前一项和下一项的内在逻辑,例如 TimeTableItem 或者任何与时间有关的东西。它们应该实现一个接口,因此 链表 实现可以利用这一点,并且不必将项目包装到自己的节点对象中。插入和移除比使用 List 实现在内部处理数组。

5

1

Mike Dunlavey 16 年前

您假设数组不能动态地重新分配。如果可以的话,数组会获胜,因为它不需要大于k个项(加上一个恒定的开销),也因为它不需要指针的每项存储。