Как List устроен под копотом?

Подробное устройство List<T> в C#

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

Основные внутренние поля

public class List<T>
{
    private T[] _items;      // Внутренний массив для хранения элементов
    private int _size;       // Текущее количество элементов в списке
    private int _version;    // Счетчик изменений для обеспечения консистентности итераторов
}

Ключевой момент: емкость (Capacity) определяется длиной массива _items, а количество элементов (Count) — значением _size.

Механизм динамического расширения

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

public void Add(T item)
{
    if (_size == _items.Length)
    {
        EnsureCapacity(_size + 1); // Проверка необходимости расширения
    }
    _items[_size++] = item;
    _version++;
}

private void EnsureCapacity(int min)
{
    if (_items.Length < min)
    {
        int newCapacity = _items.Length == 0 ? 4 : _items.Length * 2;
        Array.Resize(ref _items, newCapacity); // Создание нового массива и копирование
    }
}

Важные особенности расширения:

• Начальная емкость по умолчанию — 4 элемента (если не задана явно)
• При исчерпании места создается новый массив в 2 раза больше предыдущего
• Все элементы копируются из старого массива в новый (операция O(n))
• Старый массив становится объектом для сборки мусора

Критические аспекты производительности

1. Доступ по индексу — O(1), так как это прямое обращение к элементу массива
2. Добавление в конец — амортизированное O(1), но при расширении — O(n)
3. Вставка/удаление в середине — O(n), так как требует сдвига элементов
4. Итерация — эффективная, так как проходит по непрерывному блоку памяти

Рекомендации по оптимизации

// Плохо: много расширений при добавлении 1000 элементов
var slowList = new List<int>();
for (int i = 0; i < 1000; i++) slowList.Add(i); // 10 расширений массива

// Хорошо: задаем начальную емкость
var fastList = new List<int>(1000);
for (int i = 0; i < 1000; i++) fastList.Add(i); // 0 расширений

Специфические детали реализации

Модификация во время итерации:

List<int> list = new List<int> { 1, 2, 3 };
foreach (var item in list)
{
    list.Add(item * 2); // InvalidOperationException: Collection was modified
}

Исключение возникает из-за проверки поля _version, которое изменяется при каждой модификации списка.

Метод TrimExcess:

list.TrimExcess(); // Уменьшает Capacity до Count, если разница более 10%

Этот метод полезен для экономии памяти, когда дальнейшее расширение не ожидается.

Сравнение с аналогичными структурами

• Массив (T[]) — фиксированный размер, но более эффективен для хранения
• LinkedList<T> — эффективные вставки/удаления в любом месте (O(1)), но медленный доступ по индексу (O(n))
• Collection<T> — базовый класс с виртуальными методами для наследования

Практические выводы

1. Всегда оценивайте примерное количество элементов и задавайте начальную емкость через List<T>(int capacity)
2. Избегайте частых вставок/удалений в середине больших списков
3. Используйте Capacity для мониторинга избыточного выделения памяти
4. Помните о копировании элементов при расширении — это может быть дорого для сложных объектов

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