List operations complexity

Question

I have always thought that List<T> in C#is a classic linked list, but recently I read that it is actually backed by array internally.

Does this mean that when we do insert to the start of the list it is O(n) operation because other elements needs to be moved one position further like in simple array? And every time we add a new item the new array with bigger capacity is created? Or it is some hybrid like ArrayList in Java?

If anyone has some link with complexity for C# List operations it would be good.

Answer 1

Your assumption is right. You can find the complexities of the operations documented on MSDN:

List<T>.Insert:

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

List<T>.Add:

If Count already equals Capacity, the capacity of the List is increased by automatically reallocating the internal array, and the existing elements are copied to the new array before the new element is added.

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

Yes, the capacity is increased as needed, but no, the capacity is not increased for every Add operation. As we can see in the documentation of the constructor in the reference source, lists have a certain base capacity, and the capacity is doubled every time it is exceeded:

// Constructs a List. The list is initially empty and has a capacity
// of zero. Upon adding the first element to the list the capacity is
// increased to 16, and then increased in multiples of two as required.
public List() {
    ...
}

So, in a nutshell, choosing the right list depends on your needs. This answer compares the complexities of common operations in array-based lists (such as List<T>) and linked lists (such as LinkedList<T>):

• Asymptotic complexity of .NET collection classes