Secret functions of the collection .Net List

Secret functions of the collection .Net List

Why even have an idea about the work of these collections and their features:

  • knowing the nuances will allow you to choose a particular collection more consciously, and when using them, you will understand the computational complexity of the operations performed and/or memory consumption
  • it is useful to understand what decisions were made by the authors of the original collections, studying the code of experienced colleagues, allows you to optimize your own solutions in places
  • in the end, it happens that people ask about it at interviews

Below we will look at the List collection, and in future articles — other collections.

Disclaimer: further, the source codes are given in the volume necessary to illustrate the nuances of the collections under consideration. Comments, validation of values, some special cases, etc. are omitted further in places. Curious readers can get acquainted with the sources in full in a publicly available repository.

List

Perhaps this collection is used every time you need to work with a variable number of objects of the same type, since the good old arrays are not too convenient for this.

So, what is inside:

public class List : IList, IList, IReadOnlyList
{
    internal T[] _items;
    internal int _size;
    private static readonly T[] s_emptyArray = new T[0];
    public List()
    {
      _items = s_emptyArray;
    }

    public List(int capacity)
    {
        if (capacity == 0)
            _items = s_emptyArray;
        else
            _items = new T[capacity];
    }

We see that the same array is located inside and the actual number of list items in the variable is separately accounted for _size. In this case, the default constructor initializes the internal array with zero elements, but there is also a constructor that allows you to explicitly set the number of elements, which will lead to the creation of an array of the appropriate size.

In this review, I will not give an example, but there is also a constructor that accepts an IEnumerable instance as input, which sequentially adds elements to the collection, while there is a simplified branch for the case when an ICollection instance was passed, because the Count property allows you to immediately create an array of the desired size and copy elements into it.

What happens when you try to add an element?

private const int DefaultCapacity = 4;
public void Add(T item)
{
    T[] array = _items;
    int size = _size;
    if (size < _items.Length)
    {
        _size = size + 1;
        array[size] = item;
    }
    else
    {
        AddWithResize(item);
    }
}

private void AddWithResize(T item)
{
    Grow(_size + 1);
    _size = _size + 1;
    _items[_size] = item;
}

private void Grow(int capacity)
{
    int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;
    if (newcapacity > Array.MaxLength)
        newcapacity = Array.MaxLength;
    if (newcapacity < capacity)
        newcapacity = capacity;
    Capacity = newcapacity;
}

So, in an optimistic scenario (the current size of the array allows you to put another element in it), the counter of the number of elements increases, and another value is added to the array.

In the case when the array is completely full, it will be forcibly enlarged. In this case, the array with 0 elements will be increased to the default size (in the current version — 4), but then the array will double each time relative to the current size. But how exactly will this be done? Let’s take a closer look at the Capacity property.

public int Capacity

{
    get => _items.Length;
    set
    {
        if (value < _size)
        {
            // выбрасывается исключение
        }
        if (value != _items.Length)
        {
            if (value > 0)
            {
                T[] newItems = new T[value];
                if (_size > 0)
                {
                    Array.Copy(_items, newItems, _size);
                }
                _items = newItems;
            }
            else
            {
                _items = s_emptyArray;
            }
        }
    }
}

Working with the Capacity property, we can check and manipulate the size of the array hidden inside the List (the main thing is not to try to make it smaller than the current number of elements). When the size of the internal array increases, a new array of the specified size will be allocated, where by the Array method.Copy (the complexity of which, as the documentation suggests, is O(n)) the current array will be copied.

Additional methods:

Clearing the array

public void Clear()
{
    if (RuntimeHelpers.IsReferenceOrContainsReferences())
    {
        int size = _size;
        _size = 0;
        if (size > 0)
        {
            Array.Clear(_items, 0, size);
        }
    }
    else
    {
        _size = 0;
    }
}

Here we see that the number of list items becomes zero, and if the array or its elements contain reference types, they are cleared for the garbage collector. Note that otherwise there is no forced “zeroing”, the logic of the class will not allow access to the array values outside the current number of elements in the usual way.

Inserting an element

public void Insert(int index, T item)
{
    if (_size == _items.Length)
        Grow(_size + 1);
    if (index < _size)
        Array.Copy(_items, index, _items, index + 1, _size - index);
    _items[index] = item;
    _size++;
}

When trying to insert, if there is such a need, the internal array will be enlarged, then the array elements will be copied by one position, starting from the index where the new element is supposed to be inserted, then the new element will be placed in the array.

I will not give the insertion of a set of elements (InsertRange), I will only note that the logic is generally the same — the array will be increased to the required value if necessary, the current elements will be moved, and the new ones will be copied to the enlarged array, starting from the target position.

Deleting an element (RemoveAt) or a set of elements (RemoveRange) by position will also not be given, in essence they are the opposite of insertion, only an increase in the size of the array, of course, does not occur.

Conclusions

Computational complexity

Below is the complexity of operations for a List, inside which an array of size N is allocated, filled by the value of S. The complexity is given, among other things, for operations that were not considered above, due to the fact that their implementation does not differ from the methods already considered or relies on them. Methods of searching, checking for the presence of elements, etc. are not given for triviality.

Operations of the List collection .Net Core

Operations of the List collection .Net Core

What practical conclusions can be drawn from all of the above:

1. Remember that inside the List is an array, not a linked list. It is enough to imagine how certain operations can be performed on an array in order to assess the complexity of a particular operation.

2. If appropriate, initialize the List by specifying the estimated size of the collection. If you know in advance the order of the number of items that are supposed to be placed in the collection, use this. This knowledge will significantly save on operations related to changing the size of the array.

3. The type of values stored in the List may affect the computational complexity of the operations performed. For reference types, additional processing takes place in places.

4. The considered sections of the code of methods that modify the collection quite clearly show the lack of guarantees of thread safety. Access to the _size variable, which determines the size of the array, to the array itself and its elements is not synchronized in any way. As a consequence, an attempt to simultaneously modify a collection from multiple threads may have side effects. To exclude them, you can use collections from the System namespace.Collections.Concurrent or, for special cases, implement your own thread-safe collections.

Outsourced Development Services | Unreal Engine Development

Ready to see us in action:

More To Explore

IWanta.tech
Logo
Enable registration in settings - general
Have any project in mind?

Contact us:

small_c_popup.png