Remove, Dictionary

In C#, Dictionary and List both have Remove methods, but the performance dramatically differs. We see how removal methods perform.

Dictionary advantage

If a program needs to remove elements from a collection often, using a Dictionary may be worthwhile. The benchmark here helps us understand this.

Example

It is important to know the syntax for removing an entry from a Dictionary. We do not need to know the value for the key, or any index value—just the key itself.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Step 1: create a dictionary.
        var entries = new Dictionary<string, int>();
        entries.Add("bird", 10);
        entries.Add("cat", 20);

        foreach (var entry in entries)
        {
            Console.WriteLine($"BEFORE: {entry}");
        }

        // Step 2: remove an entry.
        entries.Remove("bird");

        foreach (var entry in entries)
        {
            Console.WriteLine($"AFTER:  {entry}");
        }
    }
}
BEFORE: [bird, 10]
BEFORE: [cat, 20]
AFTER:  [cat, 20]

Benchmark

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.

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();
        // Version 1: remove from List.
        for (int i = 0; i < _max; i++)
        {
            list.RemoveAt(0);
        }
        s1.Stop();
        var s2 = Stopwatch.StartNew();
        // Version 2: remove from Dictionary.
        for (int i = 0; i < _max; i++)
        {
            dictionary.Remove(i);
        }
        s2.Stop();
        Console.WriteLine(s1.Elapsed.TotalMilliseconds);
        Console.WriteLine(s2.Elapsed.TotalMilliseconds);
    }
}
384.1117    List
  0.7749    Dictionary

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.

Summary

The List collection has a slow Remove method when it contains lots of data. The Dictionary collection meanwhile has a fast Remove method.