Have You Ever Wondered How the Hell a List Works Under the Hood?

Have you ever wondered how the hell does a list work under the hood? How would you implement a structure that can work as a list?

Let's walk through creating a custom generic list implementation, complete with key features like dynamic resizing, removing, adding and of course, proper enumeration.

Building Our Custom List

public class CustomList<T> : IEnumerable<T>
{
    private T[] _items;
    private int _count;

    public CustomList(int capacity)
    {
        _items = new T[capacity];
        _count = 0;
    }

    public int Count => _count;
}

Obviously, a list holds an array data structure under the hood, and we keep track of how many elements have been added using the _count field. This is important, because the array might have a capacity of 10, but if we've only added 3 elements, then _count will be 3.

Adding Elements

public void Add(T item)
{
    if (_count == _items.Length)
    {
        Array.Resize(ref _items, _items.Length * 2);

        _items[_count++] = item;

        return;
    }

    _items[_count++] = item;
}

When we add an element, and the array is already full, we resize the array to double its current size. This is what actually happens too. It's worth noting that the Array.Resize creates a new array with the specified size, copies all elements from the old array to the new one using Array.Copy, and finally sets the reference to point the new array. As you may already have figured out, this takes O(n) time, as it has to copy all elements from the old array to the new one.

Remove Elements

To remove an element, we first need to find it and then shift all elements one position back.

public void Remove(T item)
{
    var index = Array.IndexOf(_items, item);

    if (index == -1)
    {
        return;
    }

    for (var i = index; i < _count - 1; i++) 
    {
        _items[i] = _items[i + 1];
    }

    _count--;
}

Indexer

public T this[int index]
{
    get
    {
        if (index < 0 || index >= _count)
        {
            throw new IndexOutOfRangeException();
        }

        return _items[index];
    }
    set
    {
        if (index < 0 || index >= _count)
        {
            throw new IndexOutOfRangeException();
        }

        // value here represents the value being assigned to the specified index
        // e.g. customList[0] = 42;
        // 42 is the value
        _items[index] = value;
    }
}

You can even use a string, for whatever reason, parse it as an integer and then access the element from the array.

public T this[string index]
{
    get
    {
        if (!int.TryParse(index, out var i))
        {
            throw new InvalidOperationException("Index must be a number");
        }
        
        // reuse the above getter
        return this[i];
    }
    set
    {
        if (!int.TryParse(index, out var i))
        {
            throw new InvalidOperationException("Index must be a number");
        }
        
        // reuse the above setter
        this[i] = value;
    }
}

which means you can now do this:

customList["0"] = 42;

and it would compile, no issues at all! :D

Implementing Enumeration

Currently, we don't support the foreach loops. We need to implement the IEnumerable<T> interface:

public IEnumerator<T> GetEnumerator()
{
    return new CustomEnumerator(this);
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

Let's now create the CustomEnumerator itself, which is going to be a STRUCT, and I will explain why we picked a struct instead of a class in a bit.

public struct CustomEnumerator : IEnumerator<T> 
{
    private readonly CustomList<T> _list;
    private int _index;
    private T _current;

    internal CustomEnumerator(CustomList<T> list)
    {
        _list = list;
        _index = -1;
        _current = default;
    }

    public bool MoveNext()
    {
        ++_index;

        if (_index < _list.Count)
        {
            _current = _list[_index];
            return true;
        }

        return false;
    }

    public T Current => _current;

    object IEnumerator.Current => Current;

    void IEnumerator.Reset()
    {
        _index = -1;
        _current = default;
    }

    public void Dispose()
    {
        // nothing to dispose here
    }
}

So, first of all, why a struct for the enumerator?

Well, obviously, for performance reasons! Using a struct avoids the overhead of heap allocation and ultimately garbage collection that would occur with a class. Since enumerators are typically short-lived and created frequently (basically every time you use foreach), this optimization can significantly improve performance, especially in "tight" loops.

TrimExcess

It's worth noting here the TrimExcess method. It reduces the capacity of the collection to match its current size, freeing up memory.

How it works?

As you previously seen, whenever we reach the length of the underlying array, we double the size of it, meaning we allocate extra space. If however, you remove many elements, the capacity remains the same, meaning you're wasting memory. So what TrimExcess does, is shrinking the capacity to the actual number of elements!

public void TrimExcess()
{
    if (_count < _items.Length)
    {
        Array.Resize(ref _items, _count);
    }
}

Just keep in mind that you want to use it when you're pretty sure that the collection won't grow anymore and you want to free memory. If you use it frequently, you'll have face performance issues since Array.Resize copies all the elements from the old array to the new one. I believe the real List only trims if the saved memory would be significant (if the count is less than 90% of capacity)

Let's use our CustomList

var list = new CustomList<int>(3);
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(4);  // this will trigger a resize

list.Remove(2);

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

Console.WriteLine($"Count: {list.Count}");
Console.WriteLine($"First element: {list[0]}");

list["0"] = 10;  // no errors

Console.WriteLine($"First element after change: {list[0]}");

Output:

1
3
4
Count: 3
First element: 1
First element after change: 10

While our implementation covers the basics, the actual List in .net includes many more optimizations and features, such as binary search, sorting methods, range operations, and additional performance enhancements. But hey, today you probably learnt one or two new things! So next time you use a List in your code, you'll have a better appreciation for what's happening behind the scenes!