What is the time complexity of inserting an element into a list?

The time complexity of inserting an element into a list depends on the type of list:

• Array (e.g., std::vector in C++): insertion at the end — amortized O(1), insertion in the middle or at the beginning — O(n), as elements need to be shifted.
• Linked list (e.g., std::list in C++): insertion at an arbitrary position, if a pointer to the position is available — O(1), as only pointers are changed. If the position is determined by an index — O(n), as traversal is needed.

Example for std::list:

std::list<int> lst = {1, 2, 3};
auto it = lst.begin();
std::advance(it, 1); // move to the second element
lst.insert(it, 10); // insert 10 before the second element

Here, insertion is O(1), since the iterator already points to the desired position.