On 03/30/2011 05:30 PM, Steven Schveighoffer wrote:
Do you mean removal of an already accessed node/value? If yes, then removal
can effectively be O(1), but to first get the access (here, via a pointer)
one needs O(n) traversing the list in any case.
Of course. With SList, you need O(n) to get to the element, and then O(n) to
remove it once you find it ;)
I guess you refer to the fact that, in a slist, as opposed to doubly linked
list, one misses the 'previous' slot needed to insert or remove. Thus, one must
re-traverse to reach it. Is it the issue you're evoking?
There is a trick to avoid that, wrote it once long ago (since then I have, like
you, only used doubly-linked ones). I guess the point is, while traversing to
search a given element (by index, value, pattern matching or whatever) to
constantly keep track of the previously visited node. Thus, when you get there,
you have the needed trio (previous/current/next) available for whatever operation.
Denis
--
_________________
vita es estrany
spir.wikidot.com
