run-dev

,

Какая сложность вставки в List, Dictionary в C#

Разбор сложности операций с коллекциями важен для написания эффективного кода. В C# структуры данных List<T> и Dictionary<TKey, TValue> широко используются для хранения и обработки данных. Разберём их сложность при вставке элементов.

Сложность вставки в List

List<T> — это динамический массив, позволяющий изменять размер коллекции. Вставка элемента может происходить в конец списка или в определённую позицию.

Добавление в конец списка

Операция Add() добавляет элемент в конец списка.

List<int> list = new List<int>();
list.Add(10);
list.Add(20);

Сложность O(1) в среднем случае, так как добавление происходит в конец массива.

Вставка в середину или начало списка

Операция Insert(index, item) вставляет элемент в указанную позицию.

list.Insert(1, 15); // Вставка в середину

Сложность O(N), так как все последующие элементы сдвигаются вправо.

Сложность вставки в Dictionary<TKey, TValue>

Dictionary<TKey, TValue> реализован как хеш-таблица. Вставка элемента выполняется по ключу.

Dictionary<string, int> dict = new Dictionary<string, int>();
dict["apple"] = 1;
dict["banana"] = 2;

Добавление элемента

Операция Add(key, value) вставляет пару ключ-значение.

dict.Add("cherry", 3);

В среднем случае сложность O(1), так как элемент размещается по хешу. Однако при большом количестве коллизий возможна деградация до O(N).

Больше записей