题

我在寻找一种数据类型，可以很容易的项目增加，没有一个绩效的打击。

  • 系统。阵列 - Redim Preserve 拷贝的整个RAM从老到新的、为缓慢的作量的现有的元素
  • 系统。集合。。 -不够好？
  • 系统。集合。IList -不够好？
有帮助吗？

解决方案

只是总结一些数据结构：

系统。集合。。:类型数据结构已经过时。使用清单(t)来代替。

系统。集合。通用的。列表(t):这表示一个可调整的阵列。这个数据结构中使用一个内部阵在幕后。将项目添加到名单是O(1)只要的基础阵列还没有填补，否则其O(n+1)调整内部阵列和副本的要素。

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

添加项目的仅仅是有效的当添加到名单。插入中间部队的阵转移的所有项目，这是一个O(n)操作。删除的项目也是O(n)，因为该阵列需要转移项目落后。

系统。集合。通用的。链表(t):如果你不需要随机或索引的访问中的项目清单，例如只计划增加项目和迭代表从第一个到最后，那么一个链表是你的朋友。插入和清除量O(1)、查找是O(n)。

其他提示

你应该使用的通用名单<>(系统。集合。通用的。列表)。它的工作在 恒定的摊还时间.

它还与以下特点与阵列。

  • 快速随机访问(你可以访问的任何元素的列表中O(1))
  • 它的快速循环
  • 缓慢插入和删除的对象在开始或中间(因为它已做拷贝的整个listbelieve)

如果你需要快速插入和删除的开始或结束，使用链接表或排队

将链表< T>结构为你工作?这不是(在某些情况下)作为直观的，因为一直阵列，但是很快。

  • AddLast追加的结束
  • AddBefore/AddAfter插入到清单
  • AddFirst追加的开始

这不是快速随机访问，但是，因为你必须循环访问的结构来访问您的项目。然而，它有。ToList()and。ToArray()方法抓住一个复制的结构在清单/数组形式，因此，对于读访问，你可以做的是，在一个紧要关头。性能增加的插入可能会超过了性能下降的需要随机存取，或者它可以不是。它将完全取决于你的情况。

还有这个参考，这将有助于你决定这是正确方向走：

当使用链接表了一系列/阵列表吗？

什么是"足够好的"你吗？什么你想做这些数据结构？

没有阵结构(即O(n)access)允许插入中间没有一个O(n)运行时;插入在结束是O(n)最糟糕的是一个O(1)分摊用于自我调整数组等。.

也许hashtables(摊销O(1)访问和插入任何地方，但O(n)最糟糕的情况下插入)或树木(O(日志(n))的访问，并插入任何地点，保证)更为适合。

如果速度是你的问题，我看不出是如何选定答案是比使用原始阵列，虽然它调整自身，使用完全相同的机构将用于调整一系列(以及应采取的只是一再触摸)除非你总是添加到最后，在这种情况下，它应该做的事情一点聪明，因为它分配区块的时间，而不只是一个元素。

如果你经常添加附近开始/中收集的和不指数进入中间/端很多时候，你可能想要一个链接清单。这将有最快插入时间并将有很大的迭代的时候，它就吸在索引(例如在第3单元从结束，或者第72元)。

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