Какая асимптотика вставки в list?

Какая асимптотика вставки в list?

Хороший вопрос на понимание структур данных. Дам точный ответ с объяснением разных случаев.

Прямой ответ

Асимптотика вставки в std::list (двусвязный список):

• O(1) — если у вас уже есть итератор на позицию вставки
• O(n) — если нужно искать позицию вставки

Почему O(1) со знанием позиции?

Двусвязный список это структура:

struct Node {
    T data;
    Node* next;
    Node* prev;
};

Вставка со знанием позиции (итератора) требует:

template<class T>
void insert_at_iterator(iterator it, const T& value) {
    // 1. Создаём новый узел — O(1)
    Node* new_node = new Node(value);
    
    // 2. Обновляем 4 указателя — O(1)
    new_node->next = it.node;           // Указываем на следующий
    new_node->prev = it.node->prev;     // Указываем на предыдущий
    it.node->prev->next = new_node;     // Предыдущий теперь на новый
    it.node->prev = new_node;           // Текущий теперь на новый
}

Всего 6 операций (константа), поэтому O(1).

Пример O(1):

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

// Итератор на позицию 3
auto it = lst.begin();
++it;  // Теперь it указывает на 2
++it;  // Теперь it указывает на 3

// Вставка в позицию 3 — O(1)
lst.insert(it, 999);  // {1, 2, 999, 3, 4, 5}

O(n) при поиске позиции

Если нужно найти позицию перед вставкой:

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

// Ищем позицию после 2
auto it = std::find_if(lst.begin(), lst.end(), 
    [](int x) { return x > value_to_insert; });
// find_if требует O(n) сравнений

// Вставляем — O(1)
lst.insert(it, value_to_insert);  // {1, 2, 3, 4, 5}
// Итого: O(n) + O(1) = O(n)

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

std::vector:

• Вставка в конец: O(1) amortized
• Вставка в позицию: O(n) — нужно сдвинуть элементы
• Доступ по индексу: O(1)

std::list:

• Вставка в конец: O(1) если есть итератор
• Вставка в позицию: O(1) если есть итератор, иначе O(n)
• Доступ по индексу: O(n) — нужно идти по цепочке

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.insert(vec.begin() + 2, 999);  // O(n) — сдвиг элементов!

std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
++it; ++it;
lst.insert(it, 999);  // O(1) — просто переприсвоение указателей

Асимптотика других операций std::list

std::list<int> lst;

// push_back — O(1)
lst.push_back(10);

// push_front — O(1)
lst.push_front(5);

// pop_back — O(1)
lst.pop_back();

// pop_front — O(1)
lst.pop_front();

// find (поиск) — O(n)
auto it = std::find(lst.begin(), lst.end(), 5);

// insert со знанием позиции — O(1)
lst.insert(it, 999);

// erase со знанием позиции — O(1)
lst.erase(it);

// Access by index — O(n)
int elem = lst[5];  // НЕПРАВИЛЬНО! list не поддерживает operator[]

// Правильно:
auto it = lst.begin();
std::advance(it, 5);  // O(n)
int elem = *it;

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

list хорошо для:

• Частой вставки/удаления в середину при знанию позиции
• Работы, где не нужен случайный доступ

// Пример: очередь с приоритетом
std::list<Task> tasks;

// Находим позицию (O(n))
auto pos = std::find_if(tasks.begin(), tasks.end(), 
    [&](const Task& t) { return t.priority < task.priority; });

// Вставляем (O(1))
tasks.insert(pos, task);

list плохо для:

• Случайного доступа (нужен O(n) вместо O(1))
• Cache locality (pointer chasing)
• Памяти (overhead на два указателя на узел)

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

#include <iostream>
#include <list>
#include <vector>
#include <chrono>
#include <algorithm>

int main() {
    // Вставка в середину
    
    // vector: O(n)
    std::vector<int> vec;
    for (int i = 0; i < 1000000; i++) vec.push_back(i);
    auto start = std::chrono::high_resolution_clock::now();
    vec.insert(vec.begin() + 500000, 999);  // Сдвиг 500k элементов!
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Vector insert: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << "ms" << std::endl;
    // Output: ~10-50ms (в зависимости от машины)
    
    // list: O(1) если знаем позицию
    std::list<int> lst;
    for (int i = 0; i < 1000000; i++) lst.push_back(i);
    auto it = lst.begin();
    std::advance(it, 500000);  // O(n) для поиска позиции
    start = std::chrono::high_resolution_clock::now();
    lst.insert(it, 999);  // O(1)
    end = std::chrono::high_resolution_clock::now();
    std::cout << "List insert: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << "μs" << std::endl;
    // Output: < 1μs (просто переприсвоение указателей)
}

Важный момент: Эффективность памяти

// std::vector<int> с 1000 элементов
// Памяти: 1000 * 4 = 4000 байт

// std::list<int> с 1000 элементов
// Памяти: 1000 * (4 + 8 + 8) = 20000 байт
// (данные + next pointer + prev pointer)

// list требует в 5 раз больше памяти!
// Плюс худшая cache locality

Современный совет

В 2026 году для большинства случаев:

1. Используй vector — он почти всегда быстрее благодаря cache locality
2. Используй list — только если часто вставляешь/удаляешь в середину при знании позиции
3. Рассмотри deque — часто это лучше, чем list
4. Профилируй — не угадывай, измеряй

Вывод

Асимптотика вставки в std::list:

• O(1) со знанием итератора на позицию
• O(n) если нужно искать позицию

Это главное преимущество list перед vector для вставки, но memory overhead и cache locality часто перевешивают выгоду.