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

给出一个清单：

List SomeList = new List(); 

做：做

 SomeList.Insert(i, val); 

比。

 SomeList.Add(val); 

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

Answer 1

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

（ 来源 ）

这意味着内部数据存储为数组，因此可能需要执行insert ，因此需要移动所有元素以腾出空间，因此其复杂度为O（N），而add为a（摊销）恒定时间O（1）操作， 是的 。

总结 – 是的，它几乎总是会变慢，而且列表越大，它就越慢。

Answer 2

如有疑问，请进行实证实验：

  List 

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

Answer 3

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

List.Insert()的文档说明：

该方法是O（n）操作，其中n是Count。

List.Add()的文档说明：

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

如果您碰巧提出这个问题是因为您希望频繁地对列表的正面和背面进行添加，那么使用的相应数据结构就是Deque 。

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

Answer 4

我的第一个想法是“是的，存在性能损失，因为Insert需要将列表中的所有项目移动一个插槽以为新项目腾出空间” – 但随后我更仔细地阅读了这个问题。 所以：

通常 ， Insert需要（可能很多）更多的时间，因为它需要移动列表中已有的所有项目以便为新项目腾出空间，因此它是对列表长度的O（n）操作（如果列表填充到容量它还需要resize，但这仍然是一个O（n）操作）。 另一方面， Add只是附加新项而不需要移动任何东西，所以它更快 – 一个O（1）操作（除非列表需要resize，如上所述）。

在此特定示例中 ，列表开头为空，将没有性能差异。

当然，所有这些都没有实际意义，因为您应该根据您的意图选择方法，除非您有记录的性能问题。

Answer 5

对于一个空列表，它没有什么不同。

但对于其他任何东西，它必须更慢*因为要插入前面，整个后备arrays需要向右移动一个。

*除非Add导致Capacity增加。

Answer 6

当然可以。

由于List由数组支持，因此要在列表开头插入的任何操作都必须移动（或复制）该数组的所有其他元素。 无论列表中的项目数是多少，添加到列表末尾的操作都将以恒定时间发生。