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

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 2

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.