Что такое List в C#?

List — это универсальная коллекция, предоставляющая динамический массив с возможностью автоматического изменения размера. Это одна из самых часто используемых структур данных в C#.

Основные особенности:

• Динамический размер: В отличие от массива (T[]), List<T> автоматически увеличивает свою внутреннюю емкость при добавлении элементов.
• Доступ по индексу: Поддерживает быстрый доступ к элементам по индексу за O(1): myList[5].
• Богатый API: Содержит множество удобных методов для добавления (Add, AddRange), удаления (Remove, RemoveAt), поиска (Find, Contains) и манипуляций (Sort, Reverse).

Пример использования:

// Создание списка с начальной емкостью (оптимизация)
List<string> cities = new List<string>(capacity: 10);

// Добавление элементов
cities.Add("Москва");
cities.AddRange(new[] { "Санкт-Петербург", "Новосибирск" });

// Вставка в середину (дорогая операция O(n))
cities.Insert(1, "Екатеринбург");

// Удаление
cities.Remove("Новосибирск"); // Удаляет первое вхождение
cities.RemoveAt(0); // Удаляет элемент по индексу

// Поиск
bool hasMoscow = cities.Contains("Москва");
string firstCity = cities.Find(c => c.StartsWith("С")); // Санкт-Петербург

// Итерация
foreach (var city in cities) { /* ... */ }

Сложность операций и рекомендации:

• Доступ по индексу: O(1).
• Добавление в конец (Add): В среднем O(1). Если внутренний массив заполнен, происходит выделение нового массива (обычно в 2 раза больше) и копирование элементов (O(n)).
• Вставка/удаление в середину: O(n), так как требует сдвига всех последующих элементов.
• Когда использовать: Для хранения коллекций, где часты операции доступа по индексу и добавления в конец. Если нужны частые вставки/удаления в начале или середине, рассмотрите LinkedList<T>.