列表<T> 或 LinkedList<T>

StackOverflow https://stackoverflow.com/questions/604192

题

我需要一个包含相同类型元素列表的数据结构。需要的功能是

  • 添加
  • 获取枚举器
  • （可能）清楚

索引访问、排序、搜索、删除元素是 不需要. 。最好的收藏类别是什么？应考虑以下几个方面：性能、内存使用情况、垃圾收集器的行为。

我目前的候选人是 List<T> 和 LinkedList<T>

有帮助吗？

解决方案

简短回答
默认使用 List<T> 几乎在所有情况下。

答案稍微长一点
LinkedList<T> 与枚举这些值相比，如果您执行大量添加和删除值并且列表的大小很大，那么只会更好。如果在分析之后您发现使用 List<T> 是一个问题。

更长的答案

假设，您已确定其中之一的使用会导致性能问题。

如果你进行大量的随机访问 List<T> 无论如何，几乎总是会快得多。如果您枚举很多并且很少插入（或几乎总是在末尾附近/末尾插入） List<T> 几乎总是会更快。如果您不断在随机位置插入/删除，但在迭代列表时，已经位于或接近相关节点，并且您可能想要尝试至少数千个元素 LinkedList<T>

确定哪些值/使用情况可以转化为更好的性能在很大程度上取决于您的使用情况。微基准测试在这里可能会产生很大的误导，因为它们会掩盖链表行为的一些方面，比如节点分布在内存中，而不是很好地相邻，如果它们在测试中碰巧同时分配的话。同样预先创建 List<T> 尺寸合适可以带来很大的不同。

至于计算机科学风格的推理和大O符号（其中 真的 在这种情况下需要大 N 才有意义）

  • 手术
    • 成本 List<T>
    • 成本 LinkedList<T>
  • 插入到末尾
    • O(1)（摊余成本，根据需要分配到双倍大小）
    • 每次分配 O(1)
  • 在开始处插入
    • O(N)（尽管由于快速内存移动而完成，因此运行时行为有些复杂）
    • 复杂度(1)
  • 插入位置 x （也可以删除）
    • O(N-x)（请参阅末尾插入的注释）
    • 复杂度(1)
  • 前向枚举
    • O(N)（尽管缓存未命中最小化）
    • O(N)（尽管严重依赖于缓存局部性）
  • 反向枚举
    • 在）
    • O(N)（ LinkedList<T> 实现是双向链接的）
  • 随机访问
    • 复杂度(1)
    • 在）

内存使用很复杂，因为 List 在任何时候最多可以有 Count - 1 个多余的单元格，但是 LinkedList<T> 将消耗一个 LinkedListNode<T> 对于每个单元格，这是额外的 3 个引用（每次弹出 4/8 字节）加上通常的对象开销。在正常使用中，列表可能会获胜，但同样，如果您发现内存消耗实际上是一个问题，那么这应该只是您担心的事情。

其他提示

除非你正在处理一个巨大的结构或者你计划迭代这个东西一万亿次，否则这并不重要。只需选择一个即可 开始编码. 。如果您的应用程序稍后速度变慢，请找出原因并根据需要进行更改。

（说真的，确实如此。不是。事情。一点点。你花在寻找这个问题的答案上的每一分钟都离你拥有工作代码更近了一分钟）。

如果有人已经到了这样的地步 需要 要知道其中的区别，LinkedList 比 List 更快，如果您只需要非随机、只向前读取和附加功能，则可以使用 LinkedList。

除非您正在处理数十万或数百万个条目，并且您已经分析了您的程序以发现存在重大问题，否则您可能不会注意到两者之间的区别。

除此之外：

LinkedList<T> 提供单独的类型节点 LinkedListNode<T>, ，因此插入和删除是 O(1) 操作。

从 这里.

我会用 List<T> 因为如果所有数据都是值类型并且仍然可以很好地处理引用类型（在内部， List<T> 管理一个数组，每次空间不足时它都会增长两倍）。

LinkedList<T> 当事情不受 IO 限制时，它曾经更有意义。人们经常会引用它看似“O(1)”的性质。然而，这会降低获取节点时出现页面错误的可能性增加所带来的真实成本。

如果您可以使用数组获取连续的内存区域或 List<T> 并避免潜在的页面错误，使用现代处理器和主内存缓存线会更好。

如果您提前知道将拥有多少个元素，请使用数组。如果您很清楚有多少个元素，请使用 List<T> （并在构造函数中传递可能的上限以避免重新分配）。

我唯一一次会使用 LinkedList<T> 就是如果您需要不断地将列表中的项目增加一个值。例如，如果您正在实施 最近最少使用 缓存算法，需要在前面添加一些东西，在后面去掉一些东西。

对于小件物品来说，这确实没有什么区别。随着时间的推移，分代垃圾收集器会将分散的堆项目压缩在一起，这样链表就不会变得太糟糕。

我会选择一个 List<T> 并使用它运行，除非您发现问题（通过分析）

如果不需要索引访问，那么最好使用 LinkedList<T>. 。没有太大区别，但 LinkedList 的附加速度可能更快。

鉴于您对接口的要求，您应该使用 ICollection<T> 在代码中的任何地方，而不是引用特定的具体类。

原因是如果你使用 List 那么你可能会编写一堆使用的代码 l[0] 获得第一个项目。另一方面，如果您使用 LinkedList 那么您可以将呼叫转接到 AddLast 贯穿您的代码。为了保留切换的选择，您需要避免意外地依赖于您并不真正需要的功能。您需要使用两个容器都可以支持的接口。

所以写一个这样的类：

public static class Collections
{
    public static ICollection<T> Make<T>()
    {
        return new List<T>();
    }
}

然后每当您需要集合时，请执行以下操作：

ICollection<int> c = Collections.Make<int>();

将您选择的容器与程序的其余部分隔离。现在，当您分析并改变主意时，您只需编辑 Make<T> 方法。

LinkedList 将带来更多的内存开销（对于节点），但如果您在中间插入许多元素，效果会更好。链表也需要更多的内存分配，因为 LinkedListNode 是一个类并且是动态分配的。如果您不插入元素（只是附加），我会使用列表。列表的附加速度应该一样快或更快，尽管有时需要放大。

如果你的数组足够大，那么你需要自己推出......否则就使用列表。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top