Remove ElementUnderstand element removal methods on Dictionary and List. Remove on Dictionary is faster than on List.
This page was last reviewed on Dec 7, 2021.
Remove elements. In C#, Dictionary and List both have Remove methods, but the performance dramatically differs. We see how removal methods perform.
List Remove
Shows a list
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 program. To help us understand the issue, this program adds 3 elements to a List. It removes the first element. This causes the remaining 2 elements to shift forward.Shows a list
using System; using System.Collections.Generic; class Program { static void Main() { var elementsShiftForward = new List<int>(); // Add 3 elements. elementsShiftForward.Add(1); elementsShiftForward.Add(2); elementsShiftForward.Add(3); // Remove first element, causing the elements to shift forward. elementsShiftForward.RemoveAt(0); // Print elements. foreach (var element in elementsShiftForward) { Console.WriteLine(element); } } }
2 3
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.
Tip The Stopwatch type is used to time the removal of all of the elements. Its final timings are printed to the console.
And At the end of the program, neither the List nor the Dictionary contain any elements.
Info The total milliseconds for the removal of all elements is displayed at the program's termination.
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.
And The Dictionary contains each element indexed with a hash code using a bucket array.
Thus This means when an element is removed, only a small array (of collisions) will need to be changed.
A summary. The List collection has a slow Remove method when it contains lots of data. The Dictionary collection meanwhile has a fast Remove method.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Dec 7, 2021 (image).
© 2007-2024 Sam Allen.