Ответ
Вставка элемента в std::list (двусвязный список) в точке, на которую указывает итератор, имеет амортизированную константную сложность O(1).
Почему O(1)? Вставка требует только перенаправления нескольких указателей соседних узлов, без необходимости сдвигать другие элементы в памяти.
Примеры операций вставки:
#include <list>
#include <iterator> // для std::advance
std::list<int> myList = {1, 2, 4};
// Вставка в начало или конец - O(1)
myList.push_front(0); // Список: {0, 1, 2, 4}
myList.push_back(5); // Список: {0, 1, 2, 4, 5}
// Вставка по итератору - O(1) для самой операции вставки
auto it = myList.begin();
std::advance(it, 3); // Перемещение итератора - O(n) операция!
myList.insert(it, 3); // Вставка '3' перед '4' - O(1). Список: {0, 1, 2, 3, 4, 5}Ключевой нюанс: Хотя операция insert сама по себе O(1), получение итератора на нужную позицию (например, с помощью std::advance) может занять O(n) времени, так как std::list не поддерживает произвольный доступ. Поэтому общая сложность вставки в произвольную позицию часто составляет O(n).