What is the worst-case time complexity of deleting elements from a list?

In the worst case, removing an element from a list (for example, std::vector in C++) has a time complexity of O(n). This is because, after removing the element, all subsequent elements need to be shifted one position to the left to fill the gap.

For linked lists (for example, std::list), removing an element by iterator occurs in O(1) time, since there is no need to shift elements, but finding the element to remove can take O(n) if the iterator is not known in advance.

Example for std::vector:

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 2); // remove element at index 2
// After removal, elements at indices 3 and 4 shift left

Thus, in the worst case, removal from a dynamic array is O(n).