Почему List может расширятся?

Отличный вопрос, который касается фундаментальной структуры данных в C# и .NET, а значит, и в Unity. Ответ раскрывает важные аспекты производительности и управления памятью, критичные для разработки игр.

Принцип работы List<T> и его "расширяемость"

Короткий ответ: List<T> может расширяться, потому что внутри он использует обычный массив (T[]), и когда его внутренняя ёмкость (Capacity) исчерпана, он создаёт новый массив большего размера, копирует в него все старые элементы и заменяет старый массив новым. Это ключевой механизм.

Но давайте разберем подробнее, почему это сделано именно так и как этим управлять.

1. Внутреннее устройство: массив и две ключевые переменные

List<T> по своей сути является обёрткой (wrapper) над массивом, которая добавляет удобство динамического изменения размера. Внутри он хранит:

• Массив T[] _items: Это основа, где физически лежат данные. Его длина — это ёмкость (Capacity).
• Целое число _size: Это количество (Count) фактически добавленных элементов. Всегда Count <= Capacity.

Когда вы создаёте List без указания ёмкости, обычно выделяется массив небольшого размера (например, 4 или 0 элементов, в зависимости от версии .NET).

// Внутри это примерно так:
public class List<T>
{
    private T[] _items; // Внутренний массив
    private int _size;   // Текущее количество элементов

    public int Capacity { get { return _items.Length; } }
    public int Count { get { return _size; } }
}

2. Процесс расширения (Resizing)

Когда вы добавляете элемент методом Add(), происходит следующее:

1. Проверяется, не равен ли _size (Count) _items.Length (Capacity). Если есть свободное место в массиве (_size < Capacity), элемент просто помещается в массив по индексу _size, и _size увеличивается на 1. Это операция O(1) — очень быстрая.
2. Если места нет (_size == Capacity), запускается алгоритм расширения:

    *   Вычисляется **новая ёмкость**. Стандартная стратегия — **удвоение текущей Capacity** (например, с 4 до 8). Это компромисс между производительностью (минимизация копирований) и использованием памяти.
    *   **Выделяется новый массив** нового размера в управляемой куче (managed heap).
    *   Все существующие элементы из старого массива **копируются** в новый с помощью `Array.Copy`. Это операция **O(n)**, относительно медленная.
    *   Старый массив становится кандидатом на сборку мусора (GC).
    *   Ссылка `_items` теперь указывает на новый массив.
    *   Новый элемент добавляется, и `_size` увеличивается.

Именно этот процесс копирования и делает расширение "дорогой" операцией.

3. Почему удвоение? Стратегия роста

Удвоение — это классическая стратегия амортизированной константной сложности O(1) для операции Add. Хотя отдельные операции расширения дороги (O(n)), они происходят всё реже и реже (при размерах 4, 8, 16, 32...). В среднем, стоимость добавления одного элемента остаётся постоянной. Альтернативой могло бы быть увеличение на фиксированную величину, но это привело бы к более частым и в итоге более затратным копированиям.

4. Критическая важность для Unity и разработки игр

В игровой разработке неконтролируемое расширение List может вызывать просадки производительности (spikes) по двум причинам:

1. Само копирование данных при больших размерах (тысячи элементов) требует времени.
2. Выделение новой памяти и сборка мусора (Garbage Collection). Каждое расширение создает новый массив, а старый становится мусором. Частые вызовы GC — главный враг плавного FPS в Unity.

Поэтому в Unity крайне важно управлять ёмкостью List'а:

// ПЛОХО: Будет многократно расширяться и вызывать GC.
List<Enemy> enemies = new List<Enemy>();
for (int i = 0; i < 1000; i++) {
    enemies.Add(new Enemy()); // Много переаллокаций!
}

// ХОРОШО: Минимизируем переаллокации и GC.
int expectedEnemyCount = 1000;
List<Enemy> enemies = new List<Enemy>(expectedEnemyCount); // Задаем начальную Capacity
for (int i = 0; i < expectedEnemyCount; i++) {
    enemies.Add(new Enemy()); // Расширения не произойдет (пока не превысим 1000)
}

// Также можно освободить лишнюю память, если список сильно уменьшился:
enemies.TrimExcess();

Вывод

List<T> расширяется благодаря стратегии динамического перераспределения массива, обычно с удвоением ёмкости. Это даёт удобство динамической работы с коллекцией, сохраняя хорошую среднюю производительность добавления. Однако для разработчика в Unity понимание этого механизма — обязательно. Неуправляемые расширения ведут к сборке мусора (GC) и просадкам FPS. Всегда, когда это возможно, следует задавать начальную ёмкость (Capacity) через конструктор, чтобы выделить память один раз и использовать List почти как высокоуровневый массив с удобным API.