Efficiently Remove Elements While Iterating in C

Modifying a collection during a standard foreach loop in C# throws an InvalidOperationException because the underlying enumerator detects that the collection has changed. This article explains the most efficient, idiomatic techniques to safely remove elements while iterating across different collection types, including using built-in methods like RemoveAll, iterating backwards via index, collecting keys for batch deletion, and leveraging LINQ.

1. The Best Approach for Lists: List<T>.RemoveAll

If you are working with a List<T>, the fastest and cleanest method is RemoveAll. It takes a Predicate<T> delegate and deletes all matching elements in a single pass (\(O(N)\) time complexity) without creating an intermediate collection.

List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6 };

// Removes all even numbers in-place
numbers.RemoveAll(n => n % 2 == 0);

Under the hood, RemoveAll shifts elements to their final positions in memory in one go, avoiding the performance penalties associated with repeated index shifts.

2. The Reverse for Loop

When working with an indexable collection (such as an array or IList<T>) where you need complex inline logic during iteration, iterate backwards using a standard for loop.

Iterating from the end to the beginning ensures that removing an element only shifts elements that have already been evaluated, preventing index misalignment or skipped items.

List<string> words = new List<string> { "apple", "banana", "cherry", "date" };

for (int i = words.Count - 1; i >= 0; i--)
{
    if (words[i].StartsWith("b"))
    {
        words.RemoveAt(i);
    }
}

Note: While memory-efficient, repeated calls to RemoveAt shift elements on every removal, leading to \(O(N^2)\) worst-case performance on large lists. Prefer RemoveAll when simple condition matching is sufficient.

3. Dictionaries and Sets: Two-Pass Deletion

Collections like Dictionary<TKey, TValue> or HashSet<T> do not support index-based iteration or RemoveAll. To remove elements, first identify the keys or items to be removed, store them in a temporary list, and then delete them.

var scores = new Dictionary<string, int>
{
    { "Alice", 85 },
    { "Bob", 40 },
    { "Charlie", 95 }
};

// Step 1: Collect keys that meet removal criteria
List<string> keysToRemove = new List<string>();
foreach (var kvp in scores)
{
    if (kvp.Value < 50)
    {
        keysToRemove.Add(kvp.Key);
    }
}

// Step 2: Remove keys from original dictionary
foreach (var key in keysToRemove)
{
    scores.Remove(key);
}

This preserves the original collection reference while safely circumventing enumerator modification errors.

4. Linked Lists: LinkedListNode<T> Traversal

For LinkedList<T>, you can iterate safely using the nodes directly. Cache the reference to the next node before removing the current one.

LinkedList<int> linkedList = new LinkedList<int>(new[] { 10, 15, 20, 25 });
LinkedListNode<int>? current = linkedList.First;

while (current != null)
{
    LinkedListNode<int>? next = current.Next;

    if (current.Value % 2 != 0)
    {
        linkedList.Remove(current); // O(1) removal
    }

    current = next;
}

Removing a LinkedListNode<T> is an \(O(1)\) operation and does not invalidate your reference to next.

5. Creating a Filtered Collection via LINQ

If mutating the existing collection in-place is not strictly required, filtering with LINQ's Where clause is often the most readable alternative.

IEnumerable<int> source = new[] { 1, 2, 3, 4, 5 };

// Materialize a new collection excluding unwanted items
List<int> result = source.Where(x => x > 2).ToList();

This pattern allocates a new collection, but it avoids side effects and works uniformly across any IEnumerable<T>.

Summary Checklist

• Use List<T>.RemoveAll for List<T> when you want optimal \(O(N)\) in-place performance.
• Use a Reverse for Loop for indexed collections requiring custom logic during deletion.
• Use Two-Pass Deletion for Dictionary<TKey, TValue> and HashSet<T>.
• Use LinkedListNode.Next Caching for LinkedList<T>.
• Use LINQ Where if creating a new collection is acceptable.