List <T>或LinkedList <T>

Question

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

• 加
• 的GetEnumerator
• (可能)清楚

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

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

Answer 1

除非你正在处理一个庞大的结构,或者你计划迭代这个东西一万亿次,否则无所谓.只需选择一个并开始编码.如果您的应用程序稍后会慢慢爬行,请找出原因然后根据需要进行更改.

(说真的,确实如此.不是.问题.最轻微的.你花在寻找这个问题的答案上的每一分钟都是一分钟,你可能已经有了工作代码).

如果有人已经达到需要知道差异的程度,LinkedList比List更快,如果你只需要非随机,仅向前阅读和附加功能,可以使用它.

Answer 2

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

LinkedList<T>如果您在枚举这些值并且列表大小很大的情况下进行大量添加和删除值,那么稍微长一点的答案会更好.如果您在分析后发现使用List<T>是一个问题,那么这应该只是您选择的一个因素.

更长的答案

假设,您已将一个或另一个的使用确定为性能问题.

你做了很多随机访问,无论如何List<T>都几乎总是快得多.如果你进行了大量的枚举并且很少插入(或者几乎总是插入到末尾附近),那么List<T>几乎总是会更快.如果你经常在随机位置插入/删除,但在迭代列表时已经在相关节点处或附近,并且至少有几千个元素你可能想尝试LinkedList<T>

确定哪些值/用量转换为更好的性能在很大程度上取决于您的使用情况.Microbenchmarks在这里可能会产生误导,因为它们会在链接列表行为的地毯方面进行刷新,就像在内存中分布的节点一样,如果碰巧在测试中一次性分配,那么它们很好地相邻.同样,List<T>使用正确的尺寸预先创建可以产生很大的不同.

至于计算机科学风格推理和大O符号(在这种情况下真正需要大N才有意义)

• 手术
  • 成本 List<T>
  • 成本 LinkedList<T>
• 插入到最后
  • O(1)(摊余成本,根据需要分配到双倍大小)
  • 每次O(1)分配
• 在开始时插入
  • O(N)(虽然做了快速内存移动所以有点复杂的运行时行为)
  • O(1)
• 插入位置x(并删除)
  • O(Nx)(见末尾插入评论)
  • O(1)
• 前瞻性
  • O(N)(虽然缓存未命中最小化)
  • O(N)(尽管严重依赖于缓存局部性)
• 反向枚举
  • 上)
  • O(N)(LinkedList<T>实施是双重联系的)
• 随机访问
  • O(1)
  • 上)

内存使用情况很复杂,因为List在任何时候都可以拥有最多Count-1多余的单元格,但是每个单元格LinkedList<T>会消耗一个LinkedListNode<T>,这是另外3个引用(弹出4/8个字节)加上通常的对象开销.在正常使用情况下,List可能会赢,但如果您发现内存消耗实际上是一个问题,那么这应该只是您担心的问题.

Answer 3

我会使用,List<T>因为如果它们是值类型并且仍然可以很好地使用引用类型,那么所有数据都将按顺序存储(在内部,List<T>管理一个每次耗尽空间时增长两倍的数组).

LinkedList<T>当事情不是IO绑定时,曾经更有意义.人们经常会引用其看似"O(1)"的性质.但是,这会降低页面错误获取节点的可能性带来的真实成本.

如果你可以使用数组获得连续的内存区域,或者List<T>避免页面错误的可能性,那么使用现代处理器和主内存缓存线会更好.

如果您事先知道有多少元素,请使用数组.如果您对多少元素有一个好主意,请使用a List<T>(并在构造函数中传递可能的上限以避免重新分配).

我唯一一次使用a LinkedList<T>是你需要不断地将列表中的项目按一个值.例如,如果您正在实现最近最少使用的缓存算法,并且需要在前面添加一些内容并将其取出.

对于小件物品,它确实不会有所作为.分代垃圾收集器会随着时间的推移将分散的堆项压缩在一起,因此链表不会太糟糕.

List<T>除非你注意到问题(通过分析),否则我会选择并运行它

Answer 4

除非您正在处理数十万或数百万条记录,并且您已经分析了您的程序以确定存在重大问题,否则您可能不会注意到两者之间的差异.

除此之外:

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

从这里开始.