C# 列表与链表与数组

我做了一些测试。我想很多人会对结果感兴趣。链接上的测试源： https ://github.com/ukushu/DataStructuresTests.git

简短的结论：

• 应该使用数组：

  • 尽可能频繁，如果可能（性能和内存优化）
  • 如果不需要添加单元格
  • 如果预期重量 < 85000b
  • 如果您需要随机访问速度

• 应该使用列表：

  • 如果您需要将单元格添加到列表的末尾（大/小）
  • 如果您需要将单元格添加到列表的开头/中间（少量）
  • 如果预期重量 < 85000b
  • 如果您需要随机访问速度
  • 如果可能，最好使用已键入的元素数进行初始化。

• 链表

  • 如果您需要在工作表的开头/中间/结尾大量添加单元格
  • 如果只需要顺序访问（随机访问不需要索引）
  • 非常适合存放相对少量的重物。对于每个单元格，您还需要为 2 个链接分配内存。

详细调查结果：

• 浅红色背景是不好的结果。
• 黄色背景——正常（平均）结果。
• 浅绿色背景是一个很好的结果。

还有一些有趣的信息：

1. LinkedList 在内部根本不是 .NET 语言中的列表。LinkedList<T>. 它甚至没有在IList<T>. 这就是为什么没有索引和与索引关联的方法的原因。

2. LinkedList<T>是一个基于节点指针的集合。在 .NET 中，这是在双向链接实现中实现的，即每个元素都引用它的前一个和后一个。还有数据将被分散的事实。工作表中的不同对象将位于 RAM 中的不同位置。这也意味着在 under 下将使用LinkedList<T>比List<T>or下更多的内存Array，从测试中可以看出。

3. Array<T>像List<T>（在 .Net 中，它是一个可调整大小的数组包装器）将 RAM 内存保留为一个长块。如果总元素大小 > 85000 字节，它将被重新分配到大对象堆。这反过来又会导致堆碎片——类似于轻微形式的内存泄漏。

4. List<T>如果在内存中创建的不是空的，而是大约超过所需大小，则内存中的内存将占用更少的内存。也就是说，如果您期望工作表应该有 1000 个单元格，那么它将作为一个包含 1000 个单元格的数据数组。如果您将其创建为空并填充多达 1000 个单元格，则需要更多，如测试所示。

重要如果有人发现错误 - 请在评论中指出。不管错误是在代码中，还是在我的测试中，还是在我的结论中。:)