Как реализован список?

Обзор реализации списка (List<T>) в C#

Список (List<T>) в C# — это динамический массив, который автоматически увеличивает свою ёмкость при добавлении элементов. Реализация находится в пространстве имён System.Collections.Generic и представляет собой обёртку над массивом с оптимизированной логикой управления памятью.

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

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

Ключевые характеристики:

• Начальная ёмкость по умолчанию — 4 элемента
• Динамическое расширение — при заполнении массива создаётся новый массив большего размера
• Коэффициент роста — обычно в 2 раза, но может варьироваться в зависимости от размера

Основные механизмы работы

1. Инициализация

// Создание списка с начальной ёмкостью
var list = new List<int>();           // Ёмкость = 4
var listWithCapacity = new List<int>(100); // Ёмкость = 100

2. Добавление элементов (Add)

public void Add(T item)
{
    if (_size < _items.Length)
    {
        _items[_size] = item;
        _size++;
    }
    else
    {
        GrowAndAdd(item);  // Увеличиваем массив и добавляем элемент
    }
    _version++;
}

Алгоритм расширения:

• Проверка необходимости увеличения ёмкости
• Создание нового массива с увеличенным размером
• Копирование элементов через Array.Copy()
• Установка новой ёмкости

3. Вставка элементов (Insert)

public void Insert(int index, T item)
{
    // Проверка границ
    if ((uint)index > (uint)_size) ThrowHelper.ThrowArgumentOutOfRangeException();
    
    if (_size == _items.Length) 
        Grow();
    
    // Сдвиг элементов вправо
    Array.Copy(_items, index, _items, index + 1, _size - index);
    
    _items[index] = item;
    _size++;
    _version++;
}

4. Удаление элементов (Remove)

public bool Remove(T item)
{
    int index = IndexOf(item);
    if (index >= 0)
    {
        RemoveAt(index);
        return true;
    }
    return false;
}

public void RemoveAt(int index)
{
    if ((uint)index >= (uint)_size) ThrowHelper.ThrowArgumentOutOfRangeException();
    
    _size--;
    if (index < _size)
    {
        // Сдвиг элементов влево
        Array.Copy(_items, index + 1, _items, index, _size - index);
    }
    _items[_size] = default(T); // Очистка ссылки для GC
    _version++;
}

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

Автоматическое управление памятью

• Метод TrimExcess() — уменьшает ёмкость до фактического размера, если занято менее 90%
• Метод EnsureCapacity() — явное увеличение ёмкости без добавления элементов
• Коэффициент роста адаптируется: для небольших списков — удвоение, для больших — меньший коэффициент

Производительность

• Доступ по индексу: O(1) — прямое обращение к массиву
• Добавление в конец: в среднем O(1), при расширении — O(n)
• Вставка/удаление в середину: O(n) из-за необходимости сдвига элементов
• Поиск элемента: O(n) для линейного поиска

Пример использования с демонстрацией внутренних процессов

// Создаем список с ёмкостью 2
var numbers = new List<int>(2);
Console.WriteLine($"Initial capacity: {numbers.Capacity}"); // 2

// Добавляем элементы
numbers.Add(10); // Вмещается в существующий массив
numbers.Add(20); // Вмещается в существующий массив
numbers.Add(30); // Требует расширения! Capacity станет 4

Console.WriteLine($"After third add - Capacity: {numbers.Capacity}"); // 4
Console.WriteLine($"Count: {numbers.Count}"); // 3

// Вставка со сдвигом
numbers.Insert(1, 15); // Сдвигает элементы 20 и 30 вправо

// Удаление со сдвигом
numbers.RemoveAt(0); // Сдвигает все элементы влево

Сравнение с другими коллекциями

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

Практические рекомендации

1. Задавайте начальную ёмкость, если знаете примерное количество элементов
2. Используйте Capacity и TrimExcess() для управления памятью в долгоживущих списках
3. Избегайте частых вставок/удалений в середину больших списков
4. Для частых операций поиска рассмотрите использование HashSet<T> или Dictionary<TKey, TValue>

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