Как List<T> устроен внутри и как меняет размер массива при добавлении элементов?

Устройство List<T> и изменение вместимости массива

• List<T> в .NET представляет собой динамический массив — собственную оболочку над обычным массивом
• Элементы хранятся в массиве T[], который изначально имеет фиксированную вместимость
• Когда при добавлении элементов свободное место заканчивается, происходит расширение емкости
• Как правило, новая вместимость вдвое превышает текущую, что называется геометрическим ростом
• Содержимое прежнего массива переносится в новый массив большего размера, а сама операция копирования имеет сложность O(n)
• Благодаря редким операциям расширения добавление элемента имеет амортизированную сложность O(1)
• Такой подход помогает рационально использовать память и не выполнять аллокацию при каждом добавлении
• Коллекция подходит для динамических наборов данных, в которых элементы часто добавляются в конец

Таким образом, List<T> объединяет удобство обычного массива с автоматическим расширением и контролем стоимости выделения памяти.

Подробный ответ

Основной ответ

В .NET List<T> является оболочкой над динамическим массивом и размещает элементы в непрерывной области памяти. Внутри используется стандартный массив T[], объём которого увеличивается по мере заполнения. Если при добавлении очередного элемента свободного места уже нет, создаётся более вместительный массив, после чего существующие значения копируются в него. Обычно capacity увеличивается в два раза: это уменьшает число перераспределений памяти и позволяет сохранить амортизированную сложность операции добавления.

Ключевые моменты

• Внутреннее представление — обычный массив T[]. При создании без параметров исходная capacity обычно равна 4 или 0.
• Расширение — когда свободного места недостаточно, List увеличивает capacity вдвое и переносит элементы в новый массив. Это уменьшает частоту аллокаций при добавлении большого числа значений.
• Амортизированная сложность — отдельное расширение требует копирования и занимает O(n), однако в среднем добавление выполняется за O(1), поскольку перераспределение происходит лишь время от времени.
• Оптимизация памяти — при создании List можно заранее указать capacity, а для уменьшения избыточной вместимости использовать метод TrimExcess. Это помогает избежать ненужных аллокаций и слишком большого массива.

Практический контекст

В прикладных проектах следует помнить: массовое добавление элементов может несколько раз приводить к перераспределению памяти и копированию данных, что отражается на производительности. Если предполагаемый размер коллекции известен заранее, capacity обычно задают сразу, например, new List<T>(expectedSize). Это заметно сокращает накладные расходы при крупных операциях — загрузке данных или работе с буферами.