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

C#,. NET4。

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

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

我总是认为RemovedAt是O(1)的列表。 是这样的吗?

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

RemoveO(n) ,因为它需要将列表的其余部分向下移动一个。


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

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

此方法是O(n)操作,其中n是(Count – index)。

据我所知,它应该是一个O( n )操作。 在内部,它使用Array.Copy (这是一个O( n )操作)将0之后的元素复制回列表的后备数组。 来自Reflector:

 public void RemoveAt(int index) { if (index >= this._size) { ThrowHelper.ThrowArgumentOutOfRangeException(); } this._size--; if (index < this._size) { Array.Copy(this._items, index + 1, this._items, index, this._size - index); } this._items[this._size] = default(T); this._version++; } 

因此,对于任何有效的数组索引i,它将所有后续元素从i + 1复制到i中。