Как работает List?

Как работает List<T> в C#

List<T> — это одна из самых используемых коллекций в .NET. Понимание её внутреннего устройства критически важно для написания производительного кода. За 10+ лет я видел множество разработчиков, которые теряли часы на отладку, потому что не понимали, как List работает.

Определение

List<T> — это динамический массив (dynamic array или growable array). Её главная фишка: она может менять размер во время выполнения, в отличие от обычного массива.

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

Внутри List<T> хранит три ключевых элемента:

• _items — настоящий массив T[] в памяти
• _size — сколько элементов реально в списке
• Capacity — максимальный размер текущего массива

Как добавляются элементы

Когда вы создаёте новый List, он начинает с пустого массива.

var list = new List<int>();  // Capacity = 0, Count = 0

list.Add(10);  // Capacity = 4, Count = 1
list.Add(20);  // Capacity = 4, Count = 2
list.Add(30);  // Capacity = 4, Count = 3
list.Add(40);  // Capacity = 4, Count = 4
list.Add(50);  // Capacity = 8 (переаллокация!), Count = 5

Вот ключевой момент: когда элементов становится больше, чем Capacity, List создаёт новый массив большего размера (обычно в 2 раза больше) и копирует туда все старые элементы. Это дорогая операция!

Сложность операций

• Add() в конец: O(1) amortized
• Insert(index): O(n) — нужно сдвинуть элементы
• Remove(item): O(n) — поиск + сдвиг
• RemoveAt(index): O(n) — сдвиг элементов
• Доступ по индексу []: O(1)
• Contains(): O(n) — линейный поиск

Практические примеры оптимизации

// Плохо — множество переаллокаций
var list = new List<int>();
for (int i = 0; i < 1_000_000; i++)
    list.Add(i);

// Хорошо — предзаказываем место
var list = new List<int>(1_000_000);
for (int i = 0; i < 1_000_000; i++)
    list.Add(i);

Удаление элементов

// Плохо: O(n^2)
for (int i = 0; i < list.Count; i++)
    if (list[i] % 2 == 0)
        list.RemoveAt(i);

// Хорошо: O(n)
for (int i = list.Count - 1; i >= 0; i--)
    if (list[i] % 2 == 0)
        list.RemoveAt(i);

// Лучше: RemoveAll
list.RemoveAll(x => x % 2 == 0);

Когда использовать List

Use List для:

• Частого доступа по индексу
• Добавления в конец
• Большинства общих сценариев

Не используй для:

• Частых операций с началом/серединой → используй LinkedList
• Быстрого поиска → используй HashSet, Dictionary

Выводы

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