logo标签列表

树：链表 vs 数组（效率）

arraystreeperformancelinked-listtheory
6

这是一个我无法用言语表达答案的问题。

“假设每个节点最多可以有k个子节点。v是每个节点平均拥有的子节点数量。对于哪些v值，使用链表存储子节点比使用数组更有效（以所使用的空间为标准）？为什么？”

我相信我可以用简单易懂的英语回答“为什么”，因为使用链表会更有效率，因为在填充值时只为链表中的节点分配空间，而不是像数组一样为所有节点分配空间，从而避免了创建空节点（即如果您的平均数小于最大值，则为数组中的空索引）占用内存。

因此，如果您的平均值为6个子节点，而最大值为200，则在创建树时，数组将为每个节点的所有200个子节点创建空间，但链表仅在需要时为节点分配空间。 因此，使用链表，所使用的空间将近似于平均值；使用数组，所使用的空间将达到最大值。

...我不知道何时使用数组会更有效率。 这是一个诡异的问题吗？ 我需要考虑数组在创建时需要限制总节点数吗？

5个回答
5
我不认为使用数组会更有效。这不是一个恶作剧吗？ 这不是恶作剧。考虑一下链表所具有的内存开销。链表如何实现（与数组相比）？ 另外（虽然这超出了问题的范围！），在实践中，空间消耗并不是唯一的决定因素。缓存在现代CPU中发挥着重要作用，将单个子节点存储在数组而不是链表中可以极大地提高缓存局部性（因此也能大幅度提高树的性能）。
我不确定你所说的链表开销是指什么。你是在谈论引用所需的内存吗？ - dc.
@dc：那么，链表是如何实现的？需要多少内存？ - Konrad Rudolph
5
对于许多常用的语言，数组需要分配存储k个内存地址（数据）。单向链表每个节点需要两个地址（数据和下一个节点）。双向链表每个节点需要三个地址。
假设节点A有实际的n个子节点：
  • 数组使用k个内存地址
  • 单向链表使用2n个地址
  • 双向链表使用3n个地址
值k可以让您确定2n或3n个地址与仅在数组中存储地址相比平均增益或减少。
3

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

提示：如果需要，您可以一次性分配整个数组，但通常我们分配4个条目，并在需要更多空间时将其大小加倍。

这个问题仅涉及空间，而不涉及时间。 - Konrad Rudolph
@Konrad Rudolph，确实。由于“我不认为使用数组会更有效率”，所以我提到了一个提示 :) - Nick Dandoulakis
1

我可以想象，在许多情况下，如果数据项本身具有前一个和后一个项目的内在逻辑，例如TimeTableItem或任何与时间相关的内容，使用LinkedList可能是一个非常好的主意并且非常有效。这些应该实现一个接口，因此LinkedList实现可以利用它，而不必将项目包装到自己的节点对象中。在这里插入和删除会比使用List实现更有效率，后者在内部会围绕数组进行操作。

1
你假设数组无法被动态重新分配。如果可以，数组就会胜出，因为它只需要比k个元素（加上一个常量开销）稍微大一点，并且不需要为指针分配每个元素的存储空间。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接