A few words about the implementation of List
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.
List<T> class implements:
List<T> class is defined in the
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
items- elements of the
size- the number of items that are currently in the
version- changes as the
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
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 ✨