Does List.Insert have any performance penalty?

Question

Given a list:

List<object> SomeList = new List<object>();

Does doing:

SomeList.Insert(i, val);

Vs.

SomeList.Add(val);

Has any performance penalty? If it does, how it depends on:
- i - insertion index
- SomeList.Count - The size of the list

Answer 1

I realise that this has already been thoroughly answered, but I would like to point out that this information is readily available in the MSDN documentation.

The documentation for List<T>.Insert() states:

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

The documentation for List<T>.Add() states:

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.

If you happen to be asking this question because you have a situation where you want to perform frequent adds to the front and back of a list, then the appropriate data structure to use is a Deque.

Stephen Cleary has provided a good Deque implementation here: http://nitodeque.codeplex.com/

Answer 2

The List class is the generic equivalent of the ArrayList class. It implements the IList generic interface using an array whose size is dynamically increased as required.

(source)

Meaning that the internal data is stored as an Array, and so it is likely that to perform the insertit will need to move all the elements over to make room, thus its complexity is O(N), while add is a (amortised) constant time O(1) operation, so yes.

Summary - Yes, it will almost always be slower, and it will get slower the larger your list gets.

Answer 3

My first thought was "yes, there is a performance penalty because Insert needs to move all the items in the list one slot to make room for the new item" -- but then I read the question more carefully. So:

In general, Insert takes (possibly a lot) more time because it needs to move all the items already in the list to make room for the new item, so it's an O(n) operation on the length of the list (if the list is filled to capacity it will also need to resize, but that's still an O(n) operation). On the other hand Add simply appends the new item without needing to move anything so it's faster -- an O(1) operation (unless the list needs to resize, as above).

In this specific example, where the list is empty to begin with, there will be no performance difference.

Of course all this is kind of moot because you should choose methods based on what your intent is unless you have a documented performance issue.

Answer 4

When in doubt, perform an empirical experiment:

List<object> SomeList = new List<object>();

Stopwatch sw = new Stopwatch();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Insert(0, String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
sw.Reset();

SomeList = new List<object>();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Add(String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);

The Insert takes 2800ms on my machine; the Add takes 0.8ms. So yes, Insert is much less performant.

Answer 5

Of course it does.

Since List<T> is backed by an array any operation to insert at the beginning of the list must move (or copy) all of the other elements of the array. An operation that adds to the end of the list will occur in constant time, regardless of the number of items in the list.

Answer 6

For an empty list, it is no different.

But for anything else it has to be slower* because to insert at the front, the whole backing array needs to be shifted one to the right.

*Except where the Add causes the Capacity to increase.