TheDeveloperBlog.com


C# Remove Element

Removing an element takes time. Dictionary and List both have a Remove method that has the same effect, but the performance dramatically differs. We see how the Remove method performs on these type instances.


Example. This program first adds 100,000 integers to a List and then those same integers to a Dictionary. Next it loops over those 100,000 ints and removes them all by value. The Stopwatch type is used to time the removal of all of the elements.

Stopwatch

And: At the end of the program, neither the List nor the Dictionary contain any elements.

C# program that tests Remove methods

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    const int _max = 100000;
    static void Main()
    {
	var list = new List<int>();
	for (int i = 0; i < _max; i++)
	    list.Add(i);

	var dictionary = new Dictionary<int, int>();
	for (int i = 0; i < _max; i++)
	    dictionary.Add(i, i);

	var s1 = Stopwatch.StartNew();

	for (int i = 0; i < _max; i++)
	    list.Remove(i);

	s1.Stop();
	var s2 = Stopwatch.StartNew();

	for (int i = 0; i < _max; i++)
	    dictionary.Remove(i);

	s2.Stop();
	Console.WriteLine(s1.Elapsed.TotalMilliseconds);
	Console.WriteLine(s2.Elapsed.TotalMilliseconds);
	Console.Read();
    }
}

Output

2373.9894
1.9896

The total milliseconds for the removal of all elements is displayed at the program's termination. The List required over 2 seconds to remove all its elements. The Dictionary required less than 2 ms. It was over 1000 times faster.


Discussion. A List is a contiguous collection of elements. When you remove an element from it, all following elements must be copied forward. This requires allocations and computations. For large Lists, this can be slow.

The Dictionary contains each element indexed with a hash code using a bucket array. This means when an element is removed, only a small array (of collisions) will need to be changed. Less memory is touched and performance is better.


Summary. We looked at an issue with the Remove method on popular collections. The List collection has a slow Remove method when it contains lots of data. The Dictionary collection meanwhile has a fast Remove method.