C#List从结尾删除,真的是O(n)？

Question

我读过几篇文章,声明List.RemoveAt()处于O(n)时间.

如果我这样做:

var myList = new List<int>();

/* Add many ints to the list here. */

// Remove item at end of list:
myList.RemoveAt(myList.Count - 1); // Does this line run in O(n) time?

从列表末尾删除应该是O(1),因为它只需要减少列表计数.

我是否需要编写自己的类来执行此操作,或者删除C#列表末尾的项目是否已在O(1)时间内执行？

Answer 1

通常List<T>::RemoveAt是O(N),因为需要在索引之后将元素移位到数组中的一个槽中.但是对于从列表末尾删除的特定情况,不需要移位,因此O(1)

Answer 2

删除最后一项实际上将是O(1)操作,因为仅在这种情况下List不会移动数组中的下一项.这是来自Reflector的代码:

this._size--;
if (index < this._size) // this statement is false if index equals last index in List
{
    Array.Copy(this._items, index + 1, this._items, index, this._size - index);
}
this._items[this._size] = default(T);