List.Insert是否有任何性能损失？

Question

给出一个清单:

List<object> SomeList = new List<object>();

做:做

SomeList.Insert(i, val);

比.

SomeList.Add(val);

有任何性能损失？如果是的话,它取决于:
- i- 插入索引
- SomeList.Count- 列表的大小

Answer 1

List类是ArrayList类的通用等价物.它使用一个数组实现IList泛型接口,该数组的大小根据需要动态增加.

(来源)

这意味着内部数据存储为数组,因此很可能执行insert它需要移动所有元素以腾出空间,因此其复杂性为O(N),add而是(摊销的)恒定时间O(1)操作,是的.

总结 - 是的,它几乎总是会变慢,而且列表越大,速度就越慢.

Answer 2

如有疑问,请进行实证实验:

List<object> SomeList = new List<object>();

Stopwatch sw = new Stopwatch();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Insert(0, String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
sw.Reset();

SomeList = new List<object>();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Add(String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);

插件在我的机器上需要2800毫秒; 添加需要0.8毫秒.所以是的,Insert的性能要低得多.

Answer 3

我意识到这已经得到了彻底的解答，但是我想指出的是，该信息可以在MSDN文档中找到。

List<T>.Insert()状态文档：

此方法是O（n）运算，其中n是Count。

List<T>.Add()状态文档：

如果Count小于Capacity，则此方法为O（1）操作。如果需要增加容量以容纳新元素，则此方法将成为O（n）操作，其中n为Count。

如果您碰巧问这个问题是因为您要在列表的前面和后面进行频繁的添加，那么要使用的适当数据结构是Deque。

Stephen Cleary在此处提供了一个很好的Deque实现：http : //nitodeque.codeplex.com/