Какова временная сложность операции вставки элемента в список?

Временная сложность операции вставки элемента в список зависит от типа списка и позиции вставки:

• Для динамического массива (например, std::vector в C++):

  • Вставка в конец — амортизированная сложность O(1), если не требуется расширение массива.
  • Вставка в середину или начало — O(n), так как нужно сдвинуть элементы.

• Для связного списка (например, std::list):

  • Вставка после известного узла — O(1), так как достаточно переназначить указатели.
  • Поиск позиции вставки — O(n), если позиция не известна заранее.

Пример для std::list:

std::list<int> lst = {1, 2, 3};
auto it = lst.begin();
std::advance(it, 1); // переходим ко второму элементу
lst.insert(it, 10); // вставляем 10 перед вторым элементом

Здесь вставка сама по себе O(1), но если нужно найти позицию, то поиск занимает O(n).