How does a List know that you changed it while enumerating it?

Everyone falls for that and tries to change a list while enumerating it greated by the System.InvalidOperationException: Collection was modified; enumeration operation may not execute. message. But how does the List know that you changed it? Let's find out.

Given the following code:

var list = Enumerable.Range(0, 10).ToList();

foreach (var item in list)
{
    // This will throw
    list.Add(2);

    // Or this
    list.Remove(2);

    // Or this
    list.Clear();

    // Or this
    list.Insert(2, 2);

    // Or this
    list[0] = 3;
}

We will get an System.InvalidOperationException: Collection was modified; enumeration operation may not execute. exception. So basically, every operation that mutates the list will throw an exception. But how does the List know that you changed it?

Our own small list

To understand how this works, we built our own small list. The list will have three capabilities:

  1. You can add items to it.
  2. You can enumerate it.
  3. You can set an item via an indexer
public class MyListThatHas10Items : IEnumerable<int>
{
    private readonly int[] _items = new int[10];
    private int _index;

    public void Add(int item)
    {
        _items[_index++] = item;
    }

    public int this[int index]
    {
        get => _items[index];
        set => _items[index] = value;
    }
    
    public IEnumerator<int> GetEnumerator()
    {
        return new MyListEnumerator(this);
    }
    
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private class MyListEnumerator : IEnumerator<int>
    {
        private readonly MyListThatHas10Items _list;
        private int _index = -1;

        public MyListEnumerator(MyListThatHas10Items list)
        {
            _list = list;
        }

        public bool MoveNext()
        {
            _index++;
            return _index < _list._index;
        }

        public void Reset()
        {
            _index = -1;
        }

        public int Current => _list._items[_index];

        object IEnumerator.Current => Current;

        public void Dispose() { }
    }
}

Okay that is a lot of code - but I wanted to avoid taking a List<T> as we already know that it throws an exception. So we built our own small list. To make foreach available we implemented IEnumerable<int>.

But now we can do this:

var list = new MyListThatHas10Items();
list.Add(10);
list.Add(10);
list[0] = 5;

foreach (var l in list)
{
    Console.WriteLine(l);
}

Very very cute! And it prints 5 and 10. But what happens if we change the list while enumerating it?

var list = new MyListThatHas10Items();
list.Add(10);
list.Add(10);
list[0] = 5;

foreach (var l in list)
{
    list[1] = 1000;
    Console.WriteLine(l);
}

We get no exception and it prints 5 and 1000. So our list does not throw an exception. But why does List<T> throw an exception? And this is very simple, we introduce a version field that is incremented every time the list is changed. And we check this version every time we enumerate the list. If the version is different from the version when we started enumerating, we throw an exception.

public class MyListThatHas10Items : IEnumerable<int>
{
    private readonly int[] _items = new int[10];
    private int _index;
+   private int _version;

    public void Add(int item)
    {
+       _version++;
        _items[_index++] = item;
    }

    public int this[int index]
    {
        get => _items[index];
        set
        {
+           _version++;
            _items[index] = value; 
        }
    }

    public IEnumerator<int> GetEnumerator()
    {
        return new MyListEnumerator(this);
    }
    
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private class MyListEnumerator : IEnumerator<int>
    {
        private readonly MyListThatHas10Items _list;
        private int _index = -1;
+       private readonly int _originalVersion;

        public MyListEnumerator(MyListThatHas10Items list)
        {
            _list = list;
+           _originalVersion = list._version;
        }

        public bool MoveNext()
        {
+           if (_originalVersion != _list._version)
+               throw new InvalidOperationException("Collection was modified; enumeration operation may not execute.");
            
            _index++;
            return _index < _list._index;
        }

        public void Reset()
        {
            _index = -1;
        }

        public int Current => _list._items[_index];

        object IEnumerator.Current => Current;

        public void Dispose() { }
    }
}

And now we have the same behavior as List<T>. If we re-run the code from above, we will get an exception.

Unhandled exception. System.InvalidOperationException: Collection was modified; enumeration operation may not execute.

For future reference: There is a chance that in the future there will be no _version flag on List<T> (see: https://github.com/dotnet/runtime/issues/81523). When this blog post was created, _version was still a thing.

Conclusion

The List<T> class has a version field that is incremented every time the list is changed. When you enumerate the list, the version is stored. If the version is different from the stored version, an exception is thrown. This is how the List<T> knows that you changed it while enumerating it.

How does List work under the hood in .NET?

A List is one of the most used data types in .NET. You can dynamically add elements without taking care of how that happens. But do you know what is going on under the hood?

Enabling List<T> to store large amounts of elements

List<T> is one of the most versatile collection types in .NET. As it is meant for general-purpose use, it is not optimized for any specific use case. So, if we look closely enough, we will find scenarios where it falls short. One of these scenarios is when you have lots of data. This article will look at precisely this.

Array, List, Collection, Set, ReadOnlyList - what? A comprehensive and exhaustive list of collection-like types

.NET knows a big list of collection-like types like: IEnumerable, IQueryable, IList, ICollection, Array, ISet, ImmutableArray, ReadOnlyCollection, ReadOnlyList, and many more.

This blog post will give you an exhaustive list of types in .NET and when to use what.

An error has occurred. This application may no longer respond until reloaded. Reload x