logo标签列表

List<T> 或 LinkedList<T>

.netalgorithmdata-structurescollections
6

我需要一种数据结构，它可以保存相同类型的元素列表。所需功能包括：

  • 添加
  • GetEnumerator（获取枚举器）
  • (可能) 清除

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

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

你的答案也应该在这里：https://dev59.com/yXVC5IYBdhLWcg3w1E1q - nawfal
8个回答
23

除非你处理的是一个庞大的结构或者你计划迭代这个东西一万亿次，否则它并不重要。只需选择其中之一，开始编码。如果您的应用程序稍后变得缓慢，请找出其原因并根据需要进行更改。

（说真的，它并.不.重要。你花费在寻找这个问题答案的每一分钟都是离有可工作的代码更近的一分钟）。

如果有人到达了必须知道区别的地步，LinkedList比List更快，并且仅需要非随机、只能向前读取和添加功能时可以使用。

1
兄弟，因为解释如何成为更好的开发者而被打-1分？有点严厉 :) - Rex M
1
虽然答案可能是正确的，但如果它还说明了差异，那么它将是一个更有用的答案。也许有人会偶然发现这个问题，因为他们正在使用List时遇到了糟糕的性能，并且他们算法的特定情况意味着LinkedList是合适的... - ShuggyCoUk
1
目前为止，http://www.google.co.uk/search?q=site%3Astackoverflow.com+list+linkedlist 这是第三个搜索结果。 - ShuggyCoUk
3
这个答案让我想起了我的团队中的一个开发人员。我在一家高频交易公司工作，他坚定地支持“只有在真正存在性能问题时才进行分析”的理念。问题是，每次他添加新东西时，我们都会遇到新的性能问题，因为他不关心这类问题，直到事情发生后（就像你推荐的那样）。我并不是说这不是普遍适用的好建议，但我真的认为，在不了解上下文的情况下说“它并不重要”是过早的。有时，性能是非常重要的问题。 - Dan Tao
1
@Dan，这就是暂存环境的作用。 - Rex M
显示剩余3条评论
8

简短回答

在几乎所有情况下，应该默认使用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)（虽然作为快速内存移动完成，但运行时间行为相当复杂）
    • O(1)
  • 在位置 x 插入（并删除）
    • O(N-x)（参见“在末尾插入”的注释）
    • O(1)
  • 前向枚举
    • O(N)（虽然缓存未命中最小化）
    • O(N)（虽然严重依赖于缓存局部性）
  • 反向枚举
    • O(N)
    • O(N)（LinkedList<T> 实现是双向链接的）
  • 随机访问
    • O(1)
    • O(N)

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

你也可以添加 Clear。两者的时间复杂度均为 O(n)。 - nawfal
7
我会使用List<T>，因为如果数据是值类型，它们将按顺序存储，而对于引用类型也能很好地处理（在内部，List<T>管理一个数组，每次空间不足时都会增加两倍的容量）。
当事物不受IO限制时，LinkedList<T>曾经更有意义。人们经常引用其看似“O(1)”的特性，但这忽略了获取节点时出现页面错误的真实成本。
如果您可以使用数组或List<T>获得连续的内存区域并避免潜在的页面错误，则在现代处理器和主存储器缓存线方面会更好。
如果您事先知道要有多少元素，请使用数组。如果您对元素数量有一个很好的想法，请使用List<T>（并在构造函数中传递可能的上限以避免重新分配）。

如果你需要不断地将列表中的项目向前移动一个值，那么我唯一会使用 LinkedList<T>，例如实现 最近最少使用 缓存算法时需要在前面添加内容并从末尾删除。

对于小项目，这确实不会有太大影响。分代垃圾收集器会随着时间的推移将散乱的堆项紧密地压缩在一起，因此链表不会变得太糟糕。

我会选择 List<T> 并运行它，除非你通过分析发现问题。

1
我会避免在C#中使用数组，因为它们的类型安全性很差 - 事先设置.Capacity在性能方面同样好。 - Simon Buchan
7

除非你处理的条目数量达到数十万或数百万，并且你已经分析了你的程序以确定存在主要问题，否则你可能不会注意到这两者之间的差异。

除此之外:

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

来自这里。

3
如果不需要索引访问，建议使用LinkedList<T>。两种方式差别不大，但是LinkedList在添加元素时可能更快。
实际上并非如此（除非您关心大数据集的症状性能 - “最坏情况”），堆分配和链接比列表分配到内部数组要糟糕得多。预分配，也许对于中等到大型数据集来说是这样，但同样如此。 - Simon Buchan
就像Simon说的那样，List<T>的分摊成本会更好。如果您想要稳定的附加成本，链表可能更好，尽管这非常特别。 - ShuggyCoUk
2
根据您对接口的要求，您应该在代码中使用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>方法即可。

1
不，他需要添加和可能清除。 - Daniel Earwicker
我不同意；除非你正在编写一个库或在一个大系统中有强烈的架构原因。选择一个并像它本来就是那样使用它。如果你需要改变它，就改变它并让编译器告诉你需要修复什么。过早的抽象几乎和过早的优化一样糟糕。 - Euro Micelli
1
过早的抽象是不好的，因为会增加成本。选择最简单的数据类型作为变量几乎没有任何代价。 - Daniel Earwicker
Earwicker（关于最简单的数据类型）：我同意你的观点。但是IEnumerable不是一种数据类型，而是一个最小公共接口。我认为它并不完全相同。我想进一步探讨这个问题，所以我在https://dev59.com/SkbRa4cB1Zd3GeqP3sYO上发布了这个问题，以引发一些有益的讨论。 - Euro Micelli
0
一个LinkedList会有更多的内存开销（用于节点），但如果您要在中间插入许多元素，则更好。链表还需要更多的内存分配，因为LinkedListNode是一个类并且是动态分配的。如果您不插入元素（只是追加），我会使用List。对于追加操作，列表应该与LinkedList一样快或更快，尽管它偶尔需要扩大。
0
如果你的数组足够大，需要使用自己打造的数组，否则就直接使用List。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接