list.RemoveAt(0)的通用列表有多贵？

Question

C#,. NET4.

我们有一些性能关键代码导致一些问题.它是一种经过修改的队列,实际上是由List支持的.我想知道在索引0处删除元素是多么昂贵.想到的问题是:

• 根据List的支持方式,在RemoveAt()之后是否会发生任何内存分配/解除分配以补偿列表的新大小？我知道,例如,调整阵列大小可能很昂贵(相对而言)
• 我总是想象列表的行为类似于链表,这样在零位置删除一个元素就意味着只需将列表开头参考从前一个零元素调整到以前是第一个元素(但现在是第一个元素).但是,我的"想象力"和现实并不总是一致的.

我一直认为RemovedAt是O(1)的列表.是这样的吗？

Answer 1

List<T>由一个简单的数组支持,加上一个size字段,指示该数组的哪个部分实际上正在使用.(为了未来的增长).除非您添加太多元素或调用,否则不会调整数组的大小TrimExcess.

Remove是的O(n),因为它需要将列表的其余部分向下移动一个.

相反,您可以使用LinkedList<T>(除非您使用随机访问),或编写自己的列表来跟踪前面的空白部分.

Answer 2

这是O(n).它甚至在MSDN上都这么说.

此方法是O(n)操作,其中n是(Count - index).