C# List Insert

List insert. The Insert method puts an element into your List.

Any position can be specified. We see how List.Insert performs. The Insert method on List has serious problems that may significantly degrade performance.

Example. Here I found that the Insert instance method on the List type does not have good performance in many cases. The List type is able to allocate new memory at the end quickly in Add. But for Insert, it has to adjust the following elements.

List Add

Based on:

.NET 4.5

C# program that uses List Insert

using System.Collections.Generic;

class Program
{
    static void Main()
    {
	List<long> list = new List<long>();
	for (long i = 0; i < 100000; i++)
	{
	    //
	    // Insert before first element
	    //
	    list.Insert(0, i); // SLOW
	}
    }
}

Example 2. Next, we look at code that also adds an element to the List instance, but does so at the end of the List. The previous code is not horrible. This next code is faster: it uses List in the expected and optimized way.

C# program that uses List Add

using System.Collections.Generic;

class Program
{
    static void Main()
    {
	List<long> list = new List<long>();
	for (long i = 0; i < 100000; i++)
	{
	    //
	    // Add to end
	    //
	    list.Add(i); // FAST
	}
    }
}

Benchmark. In the first example, each item inserted took almost 0.1 milliseconds more than Add. In my benchmark of 100,000 iterations for A and B, this was a big difference. Insert took over 6 seconds. Add took so little time it was reported as 0.

Note: The numbers were 6770 ms and 0 ms. Zero milliseconds isn't accurate, but at least it wasn't negative.

Benchmark of List Insert

List Insert: 6770 ms
List Add:       0 ms

Summary. The List type is not optimized for Insert, but is fast for Add. Use LinkedList or another data structure if you need to insert items at the start. Often you can sort the elements later if you need a specific order.

LinkedList

Note: Performance improved in my application when I simply call Add at the end and scan through the List backwards, and avoid Insert calls.

Related Links