Ответ
List<T> — это реализация динамического массива (resizable array). Его внутренняя работа направлена на обеспечение быстрого доступа по индексу за счёт предсказуемого использования памяти.
Внутренняя структура:
- Массив (
T[] _items): Элементы хранятся в непрерывном блоке памяти в обычном массиве. - Счётчик (
int _size): Отслеживает фактическое количество элементов в списке. - Ёмкость (
int _capacity): Отслеживает длину внутреннего массива._sizeвсегда<= _capacity.
Алгоритм добавления элементов (Add):
- Проверяется, достаточно ли места: если
_size == _capacity, то происходит увеличение ёмкости. - Увеличение ёмкости: Создаётся новый массив. Размер нового массива по умолчанию равен
_capacity * 2. (Начальная ёмкость при создании пустого списка — 0, при первом добавлении становится 4). - Все существующие элементы копируются из старого массива в новый (операция
Array.Copy). - Новый элемент помещается в массив по индексу
_size, и_sizeувеличивается на 1.
Пример, иллюстрирующий рост:
var list = new List<int>(); // _items = Array.Empty<int>(), _capacity = 0
list.Add(1); // _capacity становится 4, выделяется массив int[4], копируется 1.
list.Add(2); // _size=2, просто запись в _items[1]
list.Add(3); // _size=3
list.Add(4); // _size=4
list.Add(5); // _capacity=4, _size=4 -> НУЖЕН РОСТ. Новый _capacity = 4*2 = 8.
// Создаётся int[8], копируются 1,2,3,4, затем добавляется 5 в _items[4].Производительность (Big O):
- Доступ по индексу (get; set;): O(1) — прямое обращение к массиву.
- Добавление в конец (Add): Амортизированное O(1). Большинство операций — O(1), редкие операции с увеличением ёмкости — O(n) из-за копирования.
- Вставка/удаление в середину (Insert, RemoveAt): O(n) — требует сдвига всех последующих элементов.
- Поиск по значению (Contains, IndexOf): O(n) — линейный поиск.
Best Practice: Если известно примерное количество элементов, задайте начальную ёмкость через конструктор new List<int>(1000). Это предотвратит многократные операции копирования при заполнении списка.