C# List remove from end, really O(n)?

Question

I've read a couple of articles stating that List.RemoveAt() is in O(n) time.

If I do something like:

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? 

Removing from the end of the list should be O(1), as it just needs to decrement the list count.

Do I need to write my own class to have this behavior, or does removing the item at the end of a C# list already perform in O(1) time?

Answer 1

In general List<T>::RemoveAt is O(N) because of the need to shift elements after the index up a slot in the array. But for the specific case of removing from the end of the list no shifting is needed and it is consequently O(1)

Answer 2

Removing last item will actually be O(1) operation since only in this case List doesn't shift next items in array. Here is a code from 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);