Какова асимптотическая сложность операций с списком (list) в языке C/C++?

std::list - это двусвязный список.

Преимущества:

• Быстрая вставка и удаление в любой позиции (O(1)) при наличии итератора.
• Не требует сдвига элементов при вставке/удалении.

Недостатки:

• Медленный доступ по индексу (O(n)).
• Больший расход памяти по сравнению с std::vector из-за хранения указателей.
• Итераторы могут инвалидироваться только при удалении элемента, на который они указывают (кроме clear).

Пример вставки/удаления:

#include <list>
#include <iostream>

int main() {
    std::list<int> my_list = {1, 2, 3, 4, 5};

    // Вставка в начало
    my_list.push_front(0); // O(1)

    // Удаление из конца
    my_list.pop_back(); // O(1)

    // Вставка по итератору
    auto it = my_list.begin();
    std::advance(it, 2); // Перемещение итератора на 2 позиции (O(n) для list)

    my_list.insert(it, 10); // Вставка перед итератором (O(1))

    // Удаление по итератору
    it = my_list.begin();
    std::advance(it, 3);
    my_list.erase(it); // Удаление элемента по итератору (O(1))

    return 0;
}