Ответ
Сложность операций зависит от внутренней реализации структуры данных. Вот ключевые коллекции .NET:
Списки и массивы
List<T>,T[](массив)- Доступ по индексу: O(1)
- Поиск элемента (
Contains,IndexOf): O(n) - Добавление в конец (
Add): O(1) (амортизированное, за счет увеличения емкости) - Вставка/удаление в середину (
Insert,RemoveAt): O(n) (требует сдвига элементов)
Хеш-таблицы (основанные на Dictionary<TKey, TValue>)
Dictionary<TKey, TValue>,HashSet<T>- Вставка, удаление, поиск по ключу: O(1) в среднем случае.
- В худшем случае (все ключи имеют один хеш) — O(n). Качественная реализация
GetHashCode()критически важна. - Перебор всех элементов: O(n).
Сбалансированные деревья (основанные на красно-черных деревьях)
SortedDictionary<TKey, TValue>,SortedSet<T>- Вставка, удаление, поиск: O(log n).
- Элементы хранятся в отсортированном порядке (по
IComparer<T>).
Двусвязный список
LinkedList<T>- Вставка/удаление в начало/конец или рядом с известным узлом: O(1).
- Поиск элемента по значению или по индексу: O(n).
Практический пример выбора коллекции:
// Частый поиск по ID -> Используем Dictionary
Dictionary<int, User> userCache = new();
User u = userCache[123]; // O(1)
// Частая вставка/удаление в начале/конце -> LinkedList
LinkedList<LogEntry> recentLogs = new();
recentLogs.AddFirst(newLog); // O(1)
// Нужен отсортированный набор уникальных элементов -> SortedSet
SortedSet<int> uniqueScores = new() { 95, 80, 95, 70 }; // {70, 80, 95}
bool added = uniqueScores.Add(85); // O(log n)