Как растёт список

В прошлом уроке список рос сам, сколько бы элементов в него ни добавляли. Внутри него при этом лежит обычный массив, а длина массива, как вы помните, не меняется. Как же тогда растёт список?

Вернёмся к полке. У полки есть длина — сколько книг на неё поместится. И есть книги, которые стоят на ней сейчас. Когда полка заполнилась, а книг принесли ещё, её меняют на полку вдвое длиннее и переставляют на неё все книги. Так же поступает и список:

var nums = new List<int>();
Console.WriteLine(nums.Count);    // 0
Console.WriteLine(nums.Capacity); // 0
nums.Add(7);
Console.WriteLine(nums.Count);    // 1
Console.WriteLine(nums.Capacity); // 4

Давайте разберём программу по строкам:

1. new List<int>() создаёт пустой список: в нём нет ни элементов, ни мест для них.
2. Поэтому и Count, и Capacity равны 0.
3. nums.Add(7) кладёт первый элемент. Мест не было, и список заводит внутренний массив сразу на четыре места.
4. Теперь Count равен 1, а Capacity — 4: элемент один, а мест четыре.

Два числа списка

У списка два разных числа, и их часто путают:

• Count — сколько элементов лежит в списке. Это книги на полке.
• Capacity — сколько мест во внутреннем массиве. Это длина полки.

Число мест во внутреннем массиве называют ёмкостью списка. Count никогда не бывает больше ёмкости. Пока Count меньше, Add кладёт элемент на свободное место, и ничего не копируется.

Когда места кончаются

Когда Count равен Capacity и в список добавляют ещё один элемент, список делает то же, что делают с полкой:

1. Создаёт новый массив вдвое длиннее.
2. Копирует в него все элементы старого массива.
3. Кладёт новый элемент на первое свободное место и дальше работает с новым массивом.

Первый Add в пустой список заводит четыре места, а дальше ёмкость удваивается: 4, 8, 16, 32 и так далее.

В виджете рядом с переменной nums показаны nums.Count и nums.Capacity. Это не отдельные переменные, а два числа самого списка на текущем шаге. Нажимайте «Следующий шаг» и смотрите, на каком Add меняется ёмкость.

Новый массив понадобился только на пятом Add: первые четыре элемента встали на свободные места. А RemoveAt уменьшил Count, но не Capacity: удаление не возвращает места, и массив на восемь мест остаётся.

Здесь полка и список расходятся. Настоящую полку можно нарастить, прибив рядом вторую. Массив нарастить нельзя: его длина задаётся при создании. Поэтому список всегда берёт новый массив и копирует в него элементы, а старый массив программе больше не нужен.

Почему вдвое

Этот вопрос часто задают на собеседовании: почему список растёт вдвое, а не на одно место? Добавим в пустой список 1 000 элементов и посчитаем копии — сколько раз элементы переписываются из старого массива в новый:

• если бы каждый Add добавлял одно место, он переписывал бы все прежние элементы: 0 + 1 + … + 999, то есть 499 500 копий;
• с удвоением копирование случается всего 8 раз, на ёмкостях 4, 8, 16, …, 512: 4 + 8 + … + 512 = 1 020 копий.

Выходит, для 1 000 элементов на каждый приходится около одной копии, а при любом их числе — меньше двух. Поэтому Add в среднем работает быстро, хотя изредка копирует весь список.

Места заранее

Если число элементов известно заранее, места заводят сразу: new List<string>(100). Тогда первые сто Add не создадут ни одного нового массива.

var names = new List<string>(100);
Console.WriteLine(names.Count);    // 0
Console.WriteLine(names.Capacity); // 100
List<int> nums = [1, 2, 3];
Console.WriteLine(nums.Capacity);  // 3
nums.Add(4);
Console.WriteLine(nums.Capacity);  // 6

Что здесь происходит:

1. new List<string>(100) создаёт пустой список со ста местами: Count равен 0, Capacity — 100.
2. Список из [1, 2, 3] получает ровно три места, без запаса.
3. Четвёртый элемент не помещается, и ёмкость удваивается до 6.

Частая ошибка

Завели места заранее и стали записывать элементы по индексу:

var nums = new List<int>(10);
nums[0] = 5; // ✗

Unhandled exception. System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. (Parameter 'index')

Программа компилируется, но при запуске останавливается с исключением ArgumentOutOfRangeException. Ёмкость 10 — это десять мест, а не десять элементов: Count по-прежнему 0, и элемента с индексом 0 нет. Индекс в списке должен быть меньше Count, а не Capacity, поэтому элементы в такой список кладут через Add.

Не путайте с массивом: new int[10] создаёт десять элементов, заполненных нулями, а new List<int>(10) — пустой список с десятью местами.

Главное

• Count — сколько элементов в списке, Capacity — сколько мест во внутреннем массиве.
• Когда места кончаются, список создаёт массив вдвое длиннее и копирует в него элементы; ёмкость растёт так: 4, 8, 16 и дальше.
• Список удваивает массив, поэтому копирует редко: в среднем каждый элемент копируется меньше двух раз.
• new List<int>(10) заводит места, но элементов в нём нет: индекс должен быть меньше Count.