Как работает List под капотом?

Как работает List<T> под капотом в C#

List<T> — это один из наиболее часто используемых коллекций в C#, реализующий динамически расширяемый массив. Под капотом он представляет собой обертку над обычным массивом (T[]), которая управляет его размером, предоставляя удобные методы для добавления, удаления и поиска элементов. Рассмотрим ключевые механизмы его работы.

Внутренняя структура

Основное хранилище данных — это приватный массив T[] _items. При создании List<T> без указания начальной емкости (capacity) используется массив нулевой длины или стандартный начальный размер (обычно 4 элемента в современных реализациях .NET).

private T[] _items;
private int _size; // текущее количество элементов
private int _version; // для контроля изменений при итерациях

Инициализация:

List<int> list = new List<int>(); // _items = new int[0], _size = 0
List<int> list2 = new List<int>(10); // _items = new int[10], _size = 0

Динамическое расширение (Capacity)

Когда количество элементов (_size) достигает длины массива (_items.Length) при добавлении нового элемента, происходит реаллокация массива:

1. Создается новый массив большего размера.
2. Все существующие элементы копируются в новый массив.
3. Старый массив отпускается (в конечном счете собирается GC).

Логика увеличения емкости:

• Если текущая Capacity = 0, новый размер обычно равен 4.
• Если Capacity > 0, новый размер = Capacity * 2 (двойное увеличение — стандартная стратегия для баланса между производительностью и памятью).
• При явном добавлении множества элементов через AddRange может использоваться более точный расчет.

Пример реаллокации:

List<int> list = new List<int>(2); // Capacity = 2
list.Add(1); // _size = 1, _items.Length = 2
list.Add(2); // _size = 2, _items.Length = 2
list.Add(3); // Требуется расширение: новый Capacity = 4, копирование массива

Ключевые операции и их реализация

Add(T item):

1. Проверка, есть ли свободное место (_size < _items.Length).
2. Если нет — увеличение Capacity.
3. _items[_size] = item;
4. _size++;
5. _version++; (для информирования итераторов об изменении).

Insert(int index, T item):

• Сдвиг элементов от index до конца вправо (через Array.Copy).
• Вставка нового элемента на позицию index.
• Увеличение _size и _version.

Remove(T item):

• Поиск элемента через IndexOf (линейный поиск).
• Если найден — вызов RemoveAt(index).

RemoveAt(int index):

• Сдвиг элементов от index+1 до конца влево.
• Уменьшение _size.
• Для ссылочных типов может устанавливать _items[_size] = default(T) для помощи GC.

Оптимизации и важные особенности

1. Предварительное задание Capacity: Если известно количество элементов, задание начальной Capacity через конструктор предотвращает многократные реаллокации, улучшая производительность.
2. TrimExcess(): Метод уменьшает Capacity до текущего _size, если разница значительна, оптимизируя использование памяти.
3. Внутренние массивы: При использовании ToArray() возвращается копия внутреннего массива, а не сам _items.
4. Индексатор list[index]: Просто возвращает _items[index] с проверкой диапазона.
5. Итераторы: При изменении списка во время итерации (например, в цикле foreach) изменение _version вызывает исключение для обеспечения безопасности.

Пример внутренней логики расширения

private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        int newCapacity = _items.Length == 0 ? 4 : _items.Length * 2;
        if (newCapacity < min) newCapacity = min;
        T[] newItems = new T[newCapacity];
        Array.Copy(_items, newItems, _size);
        _items = newItems;
    }
}

Сравнение с массивами (T[])

List<T> предоставляет преимущества:

• Автоматическое управление размером.
• Богатый API (Add, Remove, Find, etc.).
• Но имеет дополнительные накладные расходы на реаллокацию и проверки.

Заключение

List<T> — эффективная коллекция, балансирующая между скоростью массива и удобством динамического расширения. Понимание ее внутренней работы позволяет использовать ее оптимально: задавать начальную Capacity, избегать частых реаллокаций и предвидеть затраты на операции вставки/удаления в середине списка. В большинстве случаев List<T> является лучшим выбором для работы с последовательностями элементов в C#.