Какая сложность вставки в середину в std::list?

Сложность вставки в середину std::list

Временная сложность вставки в середину std::list составляет O(1) — это константное время при условии, что у вас уже есть итератор на позицию вставки. Это одно из ключевых преимуществ связного списка перед массивом и делает его незаменимым в определённых сценариях.

Внутреннее устройство std::list

std::list реализуется как двусвязный список (doubly-linked list):

template <typename T>
struct Node {
    T data;           // значение
    Node* next;       // указатель на следующий узел
    Node* prev;       // указатель на предыдущий узел
};

// Визуально:
// [Node1] <-> [Node2] <-> [Node3] <-> [Node4]
//   |prev      next|next      next|next

Операция вставки с известным итератором

Если у вас уже есть итератор на позицию вставки, операция требует только:

1. Создание нового узла
2. Изменение четырёх указателей (prev и next в новом узле и соседних узлах)

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // Получить итератор на третий элемент (значение 3)
    auto it = lst.begin();
    std::advance(it, 2);  // Позиционируемся на индекс 2
    
    // Вставить значение 99 перед элементом 3
    // Это O(1) операция, так как мы уже имеем итератор
    lst.insert(it, 99);
    
    // Результат: 1 2 99 3 4 5
    for (int val : lst) {
        std::cout << val << " ";
    }
}

Детали реализации вставки

// Сырый псевдокод того, как работает insert()
auto insert(iterator pos, const T& value) -> iterator {
    // 1. Создаём новый узел
    Node* new_node = new Node(value);
    
    // 2. Получаем указатели на соседей
    Node* prev_node = pos.node->prev;  // узел перед позицией
    Node* next_node = pos.node;         // узел в позиции
    
    // 3. Переустанавливаем указатели (O(1) операция)
    new_node->next = next_node;         // новый -> следующий
    new_node->prev = prev_node;         // новый <- предыдущий
    prev_node->next = new_node;         // предыдущий -> новый
    next_node->prev = new_node;         // следующий <- новый
    
    // 4. Увеличиваем размер списка
    size++;
    
    return iterator(new_node);
}

Сравнение со случаем без итератора

Если вам нужно найти позицию вставки по индексу (без готового итератора), то сложность становится O(n):

#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // ПЛОХО: O(n) из-за поиска позиции
    // Нужно пройти от начала до индекса
    auto it = lst.begin();
    std::advance(it, 2);  // O(n) операция!
    lst.insert(it, 99);   // O(1) вставка
    
    // Всего: O(n) + O(1) = O(n)
}

Это контрастирует со std::vector, где даже с известной позицией вставка требует O(n) операций для сдвига элементов.

Практические примеры

Вставка в начало (O(1)):

std::list<int> lst = {1, 2, 3};
lst.insert(lst.begin(), 0);  // O(1)
// Результат: 0 1 2 3

Вставка в конец (O(1)):

std::list<int> lst = {1, 2, 3};
lst.insert(lst.end(), 4);  // O(1)
// Результат: 1 2 3 4

Итеративное удаление и вставка (O(k) где k количество операций):

std::list<int> lst = {1, 2, 3, 4, 5};

for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it % 2 == 0) {
        // Удаление O(1), вставка O(1)
        it = lst.erase(it);     // удаляем чётное число
        it = lst.insert(it, -1); // вставляем -1
        ++it;
    } else {
        ++it;
    }
}
// Результат: 1 -1 2 -1 3 -1 4 -1 5

Сравнение с std::vector и std::deque

Когда использовать std::list

• Часто вставляете/удаляете элементы в начало или середину
• Не нужен быстрый доступ по индексу (O(n) операция)
• Нужна стабильность итераторов (итераторы не инвалидируются при вставке/удалении других элементов)
• Работаете с частыми переструктурированиями данных

// Хороший пример использования std::list
std::list<Task> task_queue;
// Постоянно добавляем и удаляем задачи из очереди
task_queue.insert(it, new_task);  // O(1)
task_queue.erase(it);              // O(1)

Вывод: std::list идеален для операций вставки-удаления в произвольных позициях, при условии, что у вас уже есть итератор. Это делает его очень мощным инструментом в арсенале C++ программиста при правильном использовании.