I gave an example: a request that is in multiple linked lists. e.g one by chronological order for quick timing out of oldest requests, and one of active requests waiting on the physical wire.

Now the timeout elapsed, so you have a pointer to a request that needs to be destroyed.

In that case, you typically use the very cheap O(1) list_del on each of the lists it's in. In STL style you pay O(N) for each list it is in. Or you conclude lists are worthless and another structure should be used. But no other structure would give you the incredibly cheap O(1) add and delete you get from lists.

sorry, my bad for not reading all the way through

Indeed, coming from Prolog/Erlang-style "most everything can be represented as a tail-call with a linked-list accumulator" programming, I'm very confused about what operations the GP is talking about. Adding/removing nodes at a position other than the head? Lookup by value? If you need these, you should be using a different data structure.

Removing from any location is O(1), as is adding to any location you have a link to.

With a real linked list at least, not with std::list.