How expensive is list.RemoveAt(0) for a generic list?

Question

C#, .NET4.

We have some performance critical code that is causing some problems. It is sort of a modified queue which is in fact being backed by a List. I was wondering how expensive removing an element at index 0 is. Questions that come to mind are:

• Depending on how List is backed, do any memory allocations/deallocations happen after at RemoveAt() for compensating for the new size of the list? I know, for example, that resizing an array can be expensive (relatively speaking)
• I always imagined Lists to behave like linked-lists, such that removing an element at the zero position would mean simply having the start-of-list reference adjusted from the previous zero element to what used to be the 1st element (but is now the first element). But, my 'imagination' and reality are not always in line.

I always assumed that RemovedAt was O(1) for Lists. Is that the case?

Answer 1

List<T> is backed by a simple array, plus a size field that indicates which portion of the array is actually in use. (to allow for future growth). The array isn't resized unless you add too many elements or call TrimExcess.

Remove is O(n), since it needs to shift the rest of the list down by one.

---

Instead, you can use a LinkedList<T> (unless you use random access), or write your own list which tracks an empty portion in front.

Answer 2

It's O(n). It even says so on MSDN.

This method is an O(n) operation, where n is (Count - index).