std::list — это двусвязный список, где каждый элемент хранит ссылку на предыдущий и следующий элементы. Это даёт эффективное добавление и удаление элементов в любой части списка, но делает доступ по индексу медленным🚩Разбор операций в `std::list` с примерами
Добавление в начало и конец — O(1)
std::list<int> lst;
lst.push_back(10); // O(1)
lst.push_front(5); // O(1)
Доступ по индексу — O(n)
auto it = std::next(lst.begin(), 2); // O(n), приходится идти от начала
std::cout << *it << std::endl;
Вставка и удаление по итератору — O(1)
auto it = lst.begin();
std::advance(it, 1); // Двигаем итератор на 1 элемент (O(n))
lst.insert(it, 8); // O(1), просто меняем указатели
lst.erase(it); // O(1), просто изменяем ссылки соседних элементов
Поиск элемента — O(n)
auto it = std::find(lst.begin(), lst.end(), 8); // O(n)
Сортировка — O(n log n)
lst.sort(); // O(n log n), потому что используется сортировка слиянием
Ставь 👍 и забирай 📚 Базу знаний