How is the algorithmic complexity of inserting an element into the middle of a std::list container evaluated?

Inserting an element into the middle of a std::list container in C++ has an algorithmic complexity of O(1), provided you already have an iterator to the insertion position.

std::list is implemented as a doubly linked list, so inserting or deleting an element by iterator is performed in constant time, as it only requires reassigning a few pointers.

However, if you need to first find the insertion position, the search time depends on the number of elements and will be O(n).

Example of insertion:

std::list<int> lst = {1, 2, 4, 5};
auto it = std::next(lst.begin(), 2); // iterator to element '4'
lst.insert(it, 3); // insert '3' before '4'
// lst now: 1, 2, 3, 4, 5