C# List Insert Mistake

The Insert method puts an element into your List. Any position can be specified. You want to see how List.Insert performs. The Insert method on List has serious problems that may significantly degrade performance.

This C# article demonstrates the Insert method on the List type. It provides benchmarks.

Insert into List

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.

Program that uses List Insert [C#]

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
	}
    }
}

Result
    Elements are inserted into the List.

Avoid Insert method

Next here 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 isn't really horrible, but this next code is far faster. It adds to the end of the List, not to the start. It uses List how it is meant to be used.

Program that uses List Add [C#]

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
	}
    }
}

Result
    Elements are added to the List.

Benchmark

I found that in the first example, each item inserted took almost a tenth of a millisecond more than Add. In my benchmark of 100,000 iterations for A and B, this was a big difference. Insert took over 6 seconds, and Add() took so little time it was reported as 0. 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

Here we saw that 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. Performance improved in my application when I simply call Add() at the end and scan through the List backwards, and avoid Insert calls.