# Особенности реализации List в C\#

List является одной из самых популярных коллекций в C\#\. Давайте разберёмся в некоторых особенностях работы с ним и посмотрим на внутреннюю реализацию его отдельных частей\.

![0995_C_Sharp_List_ru/image1.png](https://import.viva64.com/docx/blog/0995_C_Sharp_List_ru/image1.png)

## Введение

Данная статья будет посвящена полностью _List<T\>_ из пространства имён _System\.Collections\.Generic_, а если быть конкретнее, то его внутренней реализации и некоторым особенностям\. Это самая часто используемая коллекция языка\. И это не только моё мнение — так писали в своих книгах Эндрю Троелсен, Филипп Джепикс и Джон Скит\. И это понятно – с _List<T\>_ легко работать\. Он довольно гибкий и тем самым покрывает огромную часть повседневных задач программиста\. С этим также помогает большое количество методов, идущих с ним в комплекте\. А наличие LINQ ещё больше расширяет возможности данной коллекции\.

## Внутри List<T\>

Исходный код класса _List<T\>_ доступен на [GitHub](https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs)\. Это значит, что мы можем взглянуть на его реализацию\. Пройдёмся по важным аспектам\.

Класс _List<T\>_ представляет последовательный список элементов с динамически изменяемым размером\. Под капотом _List<T\>_ построен с использованием массива\.

Класс _List<T\>_ содержит 3 основных поля:

* _T\[\] \_items_ – внутренний массив, на основе которого строится список;
* _int \_size_ – хранит информацию о количестве элементов в списке;
* _int \_version_ – содержит версию коллекции\.

### Добавление элемента в список

Как уже было сказано, размер списка динамически изменяется\. Взглянем поподробнее, что же происходит при добавлении элемента в список\.

```cpp
public void Add(T item)
{
  _version++;
  T[] array = _items;
  int size = _size;
  if ((uint)size < (uint)array.Length)
  {
    _size = size + 1;
    array[size] = item;
  }
  else
  {
    AddWithResize(item);
  }
}
```

В первую очередь значение поля _\_version_ увеличивается на 1 \(смысл данного действия мы разберём чуть позже\)\. После этого происходит создание двух локальных переменных – массива _array_ с элементами типа _T_ и _size_ типа _int_\. Им присваиваются соответствующие поля\. Далее если в массиве ещё есть место для одного элемента, то происходит изменение элемента массива по индексу _size \+ 1_\. Если же размер массива не позволяет добавить ещё один элемент, то вызывается метод _AddWithResize_\.

```cpp
private void AddWithResize(T item)
{
  Debug.Assert(_size == _items.Length);
  int size = _size;
  Grow(size + 1);
  _size = size + 1;
  _items[size] = item;
}
```

Здесь вызывается метод _Grow_ для увеличения текущего размера внутреннего массива\. Далее производятся те же действия, что и в методе _Add,_ для добавления при доступном месте\.

Рассмотрим метод Grow подробнее:

```cpp
private void Grow(int capacity)
{
  ....

  int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;

  if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;

  if (newcapacity < capacity) newcapacity = capacity;

  Capacity = newcapacity;
}
```

Алгоритм работы метода _Grow_:

* если внутренний массив пуст, то ёмкость списка будет равна 4, иначе удвоенной длине массива;
* если новое значение ёмкости получается больше максимально возможной длины массива, то данная ёмкость станет равна _Array\.MaxLength_;
* если новое значение ёмкости коллекции получилось меньше текущего, то новая ёмкость станет равна текущей;
* в конце _newcapacity_ записывается в свойство _Capacity_\.

### Зачем нужно поле \_version?

Но зачем же всё\-таки нужно поле _\_version_, значение которого менялось в методе _Add_? Как уже было написано ранее, это поле, которое позволяет отслеживать версию списка\. Его значение проверяется при обходе списка\. К примеру, рассмотрим метод _ForEach_:

```cpp
public void ForEach(Action<T> action)
{
  ....
  int version = _version;

  for (int i = 0; i < _size; i++)
  {
    if (version != _version)
    {
      break;
    }
    action(_items[i]);
  }

  if (version != _version)
    ThrowHelper
      .ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
```

Перед началом обхода значение поля _\_version_ сохраняется в переменную\. Если во время обхода список будет изменён, то обход прекращается и выбрасывается исключение типа _System\.InvalidOperationException_\. Похожим образом _\_version_ отслеживается и в _List<T\>\.Enumerator_\. Поэтому изменение списка при его обходе в _foreach_ также приведёт к выбрасыванию исключения\.

### Capacity

У _List<T\>_ есть конструктор, который первым аргументом принимает число – начальную ёмкость\.

```cpp
List<int> list = new List<int>(8);
```

Если разработчик заранее знает нужный размер списка, то он может задать его\. Это избавляет от ненужных операций копирования и выделения памяти под новый массив при добавлении новых элементов\.

Кстати, размером внутреннего массива можно управлять, ещё и используя свойство _Capacity_:

```cpp
list.Capacity = 8;
```

Рассмотрим код данного свойства:

```cpp
public int Capacity
{
  get => _items.Length;
  set
  {
    if (value < _size)
    {
      ThrowHelper.ThrowArgumentOutOfRangeException(....);
    }

    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;
      }
    }
  }
}
```

Аксессор _get_ возвращает значение _\_items\.Length_, то есть длину внутреннего массива\.

Аксессор _set_ действует по следующему алгоритму:

* если _value_ меньше количества элементов в коллекции, то будет выброшено исключение;
* если _value_ не равно длине внутреннего массива и _value_ больше 0, то будет создан новый массив с ёмкостью, равной _value_;
* если количество элементов в списке больше 0, то будет выполнено копирование элементов из старого массива в новый;
* если _value_ равно 0, то полю, которое представляет собой внутренний массив, будет присвоен пустой массив\.

### Прочие особенности методов List<T\>

**Insert**

Метод Insert позволяет вставить элемент в коллекцию только в рамках начала и конца этой коллекции\. Если количество элементов в коллекции будет равно размерности внутреннего массива, то произойдёт увеличение ёмкости массива с помощью метода _Grow\(\_size \+ 1\)_\. При попытке вставить элемент на индекс, который больше _list\.Count_, будет выброшено исключение _System\.ArgumentOutOfRangeException_\.

```cpp
List<string> list = new List<string>() { "1", "2"};
list.Insert(1, "10"); // OK
list.Insert(2, "15"); // OK
list.Insert(10, 12); // throw exception
```

Подобное поведение останется даже при явном управлении размером внутреннего массива\. 

Рассмотрим пример:

```cpp
List<string> list = new List<string>() { "1", "2"};
list.Capacity = 8;
list.Insert(3, "3");
```

В свойство _Capacity_ присваивается 8, что приводит к изменению размера внутреннего массива\. Однако это не даёт возможности вставить элемент на позицию, превышающую _list\.Count_\. Результатом выполнения приведённого кода будет выбрасывание исключения\.

**Clear**

Данный метод производит очистку коллекции\. В результате этой операции свойство _Count_ будет иметь значение 0\. Элементы коллекции ссылочного типа получают значение по умолчанию\. Если элементы коллекции являются структурами и имеют поля ссылочного типа, то данные поля тоже получат значение по умолчанию\. Стоит заметить, что размер внутреннего массива остаётся неизменным\. Если до вызова _Clear_ свойство _Capacity_ было равно 8, то и после _Clear_ размер массива останется равным 8\. Для освобождения памяти, выделяемой под сам массив, необходимо после _Clear_ вызвать метод _TrimExcess_\.

**TrimExcess**

Данный метод делает размер внутреннего массива равным количеству элементов в списке\. Его стоит использовать, например, когда вы знаете, что в коллекцию больше не будут добавлены новые элементы\.

```cpp
list.Clear();
list.TrimExcess();
```

**Sort и OrderBy**

Между двумя этими методами есть несколько различий:

* метод _Sort_ принадлежит классу _List<T\>_, а метод _OrderBy_ является методом расширения из LINQ;
* метод _Sort_ модифицирует исходную коллекцию, а _OrderBy_ возвращает отсортированную копию с типом _IOrderedEnumerable<TSource\>_;
* метод _OrderBy_ производит устойчивую сортировку, а _Sort_ – нет\. Если вы используете метод _Sort_, то эквивалентные элементы могут быть переупорядочены\.

## Немного о производительности

### List<T\> против ArrayList

_List<T\>_ является обобщённым, а это значит, что мы должны при создании списка указать, с объектами какого типа он работает\.

```cpp
List<string> list = new List<string>();
```

Джеффри Рихтер в своей книге "CLR via C\#" приводит следующие преимущества обобщений:

* защита исходного кода;
* безопасность типов;
* более простой и понятный код;
* повышение производительности\.

В той же книге в начале 12\-ой главы про обобщения имеется хороший пример сравнения _List<T\>_ и его необобщённого аналога _ArrayList_\. Суть теста заключается в добавлении элемента в список и присваивании этого же элемента из списка в переменную 10 миллионов раз\.

Пример кода для тестирования _ArrayList_ со значимым типом:

```cpp
public void ValueTypeArrayList()
{
  ArrayList a = new ArrayList();
  for (Int32 n = 0; n < _count; n++)
  {
    a.Add(n);
    Int32 x = (Int32)a[n];
  }
}
```

Тестирование производилось с объектами значимых \(_Int32_\) и ссылочных \(_String_\) типов\. 

Переписав приведённый в книге код и протестировав его с помощью [BenchmarkDotNet](https://benchmarkdotnet.org/), я получил следующие результаты:

![0995_C_Sharp_List_ru/image2.png](https://import.viva64.com/docx/blog/0995_C_Sharp_List_ru/image2.png)

Из результатов видно, что c _Int32_ алгоритм _List<T\>_ работает гораздо быстрее, чем _ArrayList_\. В целых 13 раз\! Плюс с _List<T\>_ в 4 раза меньше выделяется память\.

Из\-за того что при работе _ArrayList_ производится множество операций упаковки, увеличивается и число сборок мусора\. При этом получение элемента требует выполнения распаковки\. Всё это приводит к снижению производительности\.

Разница при использовании ссылочных типов несущественная, так как нет операций упаковки и распаковки, которые являются очень тяжёлыми\. Судя по коду, небольшая разница в скорости появляется из\-за операции преобразования типов\.

### Преимущества задания Capacity

Как уже было сказано ранее, если разработчик заранее знает размер списка, то он может указать его\.

Проведём небольшой тест\.

```cpp
public void ListWithoutCapacity()
{
  for (int i = 0; i < Count; i++)
  {
    List<int> list = new List<int>();
    for (int j = 0; j < Length; j++)
    {
      list.Add(j);
    }
  }
}
```

В данном случае происходит добавление в _list_ 150 000 элементов\. Для наглядности проведём эту операцию 1000 раз\. И сравним производительность с таким же методом, но с указанным _capacity_, который равен количеству операций добавления\.

![0995_C_Sharp_List_ru/image3.png](https://import.viva64.com/docx/blog/0995_C_Sharp_List_ru/image3.png)

Из результатов видно, что затраченное время на выполнение метода без _capacity_ в 2 раза больше, чем с заранее установленным\. Также памяти выделяется почти в 4 раза больше\. Подобные действия убирают 17 ненужных операций копирования на каждой итерации внешнего цикла\.

### Как быстрее всего определить, что в списке есть элементы?

Возьмём три варианта определения того, что список непустой:

* использовать метод _Count_ из LINQ и сравнить результат с 0;
* использовать свойство _Count_ и сравнить результат с 0;
* использовать метод расширения _Any_ из LINQ\.

Проведя тестирование, получаем следующие результаты для списка из 1 500 000 элементов:

![0995_C_Sharp_List_ru/image4.png](https://import.viva64.com/docx/blog/0995_C_Sharp_List_ru/image4.png)

Самым быстрым оказался доступ к свойству _Count_, так как оно просто возвращает значение поля _\_size_\.

Метод _Count_ пытается преобразовать исходную коллекцию к _ICollection_\. При успешном преобразовании метод вернёт значение свойства _Count_\. В случае неудачи потребуется обойти всю коллекцию для высчитывания количества элементов\. К счастью, _List<T\>_ реализует данный интерфейс\.

Метод Any при обнаружении хотя бы одного элемента в коллекции вернёт _true_\. 

## Заключение

Можно сказать, что _List<T\>_ является более удобной для работы версией массива\. Например, со списком удобнее работать, когда заранее неизвестно количество элементов последовательности\.

C\# содержит ещё множество коллекций, которые помогают в работе разработчикам\. Какие\-то из них более специфичные, а какие\-то менее\. Надеюсь, что данная статья поможет вам в работе и сделает ваше понимание списков чуть лучше :\)\.