A few words about the implementation of List<T> in C#

In C# List<T> is a generic collection that is used to store any number of strongly typed objects as a list, where T is the type of objects. It allows us to perform a number of operations to find individual list items and modify them with operations such as adding, deleting or sorting.
The List<T> class implements: ICollection<T>, IEnumerable<T>, IList<T>, IReadOnlyCollection<T>, IReadOnlyList<T>, ICollection, IEnumerable and IList interface. List<T> class is defined in the System.Collection.Generic namespace.

If we look deeper, internally the List<T> stores all elements as a reference to a single array of elements of T type.

Inside of List

The most important implementation elements of the List<T>:

• items - elements of the List<T>
• size - the number of items that are currently in the List<T>
• version - changes as the List<T> is modified

The List implementation uses an underlying array for storing items. This underlying array length is called Capacity.

Adding an item to a List

Let's analyze the first operation that adds items to the List<T>. For a complete explanation, you will need to look at Capacity in depth. The Capacity value for the default constructor is equal to 4. Even if you add less elements as in our example - there is room for 4 elements in the internal array.

When we want to add a new element to the List<T>, the first step is to check - if there is enough space for it in the array. If there is, we add item to the end of our list and the version is incremented, because the array has changed.☝️

You may ask the question, what if I want to add more than 4 elements to the array? What now, since we have no more space for new items? In this case, before adding an element, the array should be resized.

Adding an element with resize

In this case, the List<T> Capacity is doubled from the previous array. A new array is created and List<T> is modified, so version is increased by 1. In the next step, the values from the old array are copied to a new array with larger Capacity in our example equal to 8.
After all these operations we have enough space to add a new element to the list.

Removing items from the List

Another operation we can perform is to remove an element from the List<T>. If we remove item with a particular index from the middle of the list, then all subsequent elements change their indexes 👇

Just like in the example, the index of element D has changed after deleting C. The size of the array decreases and the versioning mechanism remains the same. When we remove an element, as in the previous examples our version grows.

How AsSpan method works

The last issue we will touch upon in the context of the List<T> is the AsSpan() method.

Span<T> is a ref struct that can be stored only on the stack. This structure contains a pointer to a specific memory location memory and length that describes how many elements from the memory location given span has.

As we can see on the image the AsSpan() method creates a span and sets a pointer to the first element of the array that stores values of the List<T>. By wrapping the elements of the List<T> in Span<T> structure, we can operate on a subset of data without allocating additional memory. This is a great example of how using special types that allow slicing can increase the performance of our code ✨

Sources

https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/generic/list.cs
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1?view=net-6.0