whenever you have a reference to your own object, you cannot do any of the linked list operations without an O(N) penalty to go and re-find your element in the list!
Can you show an example of when you actually need to do this? Because when I need to do something like this it usually means that some container other than list is more fitting for the problem.
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.
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.
Comments
Can you show an example of when you actually need to do this? Because when I need to do something like this it usually means that some container other than list is more fitting for the problem.
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.