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 and the insertion position:

• For a dynamic array (e.g., std::vector in C++):

  • Inserting at the end — amortized O(1), if no resizing is needed.
  • Inserting in the middle or at the beginning — O(n), as elements need to be shifted.

• For a linked list (e.g., std::list):

  • Inserting after a known node — O(1), as pointers just need to be reassigned.
  • Finding the insertion position — O(n), if the position is not known in advance.

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, the insertion itself is O(1), but if you need to find the position, the search takes O(n).