A few words about the implementation of List<T> in C#
Tags: csharp, dotnet
Published: 2022-03-25 09:31:46


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<T>

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


![List Implementation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dtygqxdrgi4hdg7sj32t.png)

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

## Adding an item to a List<T>

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.


![Add elements to List](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1fgjwisgoy3kbxzylu27.png)

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


![Resize](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/17zyguj0nrwl2g0l5huy.png)

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<T>

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 👇


![Remove Elements](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1x7358uv6cnujki1b6yx.png)

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.


![Span](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b8pudo2bu1uk9ulfx361.png)

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://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](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1?view=net-6.0)