In addition to that, he's effectively comparing apples and steaks in the case of std::list.erase() vs linked-list removal. If you want O(1) removal of a random element, you use a data structure that guarantees O(1) removal of a random element (caveat: not all lists are created equal, and not all lists have O(1) removal.)

That said, it's not even removal that's O(n) here, though he may characterize it this way: it's finding the element to remove, and list searches are nearly always[1] O(n) - even with doubly-linked lists.

[1]: Except in the case of CFArray/NSArray, which is occasionally a non-list masquerading as an array - this is, of course, not a true exception as it's not a true list. (http://ridiculousfish.com/blog/posts/array.html)

> If you want O(1) removal of a random element, you use a data structure that guarantees O(1) removal of a random element

Like std::list.

It's guaranteed that insertion and removal is done in constant time. It does mean that you need an iterator pointing to the element you want to insert in front of ahead of time.

If you want to be more specific, it guarantees is that given a list of elements to insert, the insertion and deletion will be linear in the number of elements inserted or deleted (ie, independent of the size of the list being inserted into; the insertion or removal of each value passed to insert() or erase() is required to be O(1))

(That's one thing that I like about the C++ STL: It usually guarantees a certain complexity for the data structures it provides)