C# – Remove items from a list while iterating

by

There are two ways to iterate through a List<T> and remove items based on a condition:

  • Option 1: Use List.RemoveAll() and specify the conditions.
  • Option 2: Iterate backward, check conditions, and use List.RemoveAt().

These remove items from the list in an in-place manner (i.e. modify the original list) and avoid the problems you run into when doing this incorrectly (such as using a foreach or looping forward). I’ll show examples below. Then I’ll compare the performance.

Option 1 – Use List.RemoveAll() and specify the conditions

The simplest approach is to use List.RemoveAll(). You pass in a lambda with the removal conditions. It iterates through the list and removes items that meet the conditions. Then it returns the count of items removed. Here’s an example:

var list = new List<int>()
{
    1,2,3,4,5
};

list.RemoveAll(i => i < 3);

Console.WriteLine($"List after removing: {string.Join(",", list)}");
Code language: C# (cs)

This removes all integers less than 3 from the list. It outputs the following:

List after removing 2 item(s): 3,4,5Code language: plaintext (plaintext)

Option 2 – Iterate backward + List.RemoveAt()

You can remove items based on a condition by iterating backward (from the last item to the first item) with a regular for loop and using List.RemoveAt(). Here’s an example:

var list = new List<int>()
{
    1,2,3,4,5
};

for(int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] < 3)
        list.RemoveAt(i);
}

Console.WriteLine($"List after removing: {string.Join(",", list)}");
Code language: C# (cs)

This removes all integers less than 3 from the list and outputs the following:

List after removing: 3,4,5Code language: plaintext (plaintext)

Don’t loop forward

You may be wondering, is it really necessary to loop backward? The reason you have to loop backward is because removing items in a forward loop results in skipping over items. When you remove an item at index, it shifts items at index + 1 to the left by 1. Meanwhile, your loop variable keeps moving forward by 1. Hence, items get skipped. Here’s an example to show this problem:

arr = ['a','b','c']
index = 0

remove at index 0 and index++
arr = ['b','c']
index = 1Code language: plaintext (plaintext)

Notice that it skipped over item ‘b’. Looping backward eliminates this problem.

Performance comparison

List.RemoveAll() performs better than the Iterate Backward + List.RemoveAt() approach in most scenarios. Here are the performance comparison results for these two approaches in various scenarios:

Test 1 - Removing 0 items
RemoveAll (ms): 0.4266
RemoveAt (ms): 0.3588

Test 2a - Removing 10% of items from start
RemoveAll (ms): 0.3789
RemoveAt (ms): 106.8461

Test 2b - Removing 10% of items from end
RemoveAll (ms): 0.2759
RemoveAt (ms): 0.2793

Test 3a - Removing 50% of items (odd)
RemoveAll (ms): 0.3651
RemoveAt (ms): 117.2191

Test 3b - Removing 50% of items from start
RemoveAll (ms): 0.3254
RemoveAt (ms): 219.598

Test 3c - Removing 50% of items from end
RemoveAll (ms): 0.2932
RemoveAt (ms): 0.3594

Test 4a - Removing 90% of items from start
RemoveAll (ms): 0.2618
RemoveAt (ms): 81.3482

Test 4a - Removing 90% of items from end
RemoveAll (ms): 0.3022
RemoveAt (ms): 0.6094Code language: plaintext (plaintext)

As you can see, List.RemoveAll()’s performance is highly consistent (from 0.26ms to 0.42ms) whereas List.RemoveAt()’s performance varies wildly (from 0.27ms to 219ms).

To understand the performance difference, you have to know how these work internally.

  • List.RemoveAll() works by iterating through List<T>’s internal array, checking each item against the removal conditions. If it needs to remove an item, it skips overs it. If it needs to keep an item, it moves it to the left, overwriting the items to remove. It looks at and handles each item exactly once.
  • With the Iterate backward + use List.RemoveAt() approach, most of the work is being done by List.RemoveAt(). You pass in the index to remove, and this works by shifting all items from index + 1 to the left by 1 en masse by using Array.Copy() on List<T>’s internal array. This approach looks at each item once but has to potentially shift a large number of items repeatedly.

It makes sense that List.RemoveAt() would perform poorly when removing a large number of items from the start of the list. In that case, it’s copying large chunks of the internal array repeatedly.

Related Articles

Comments are closed.