On Wed, 30 Mar 2011 14:30:37 -0400, spir <denis.s...@gmail.com> wrote:
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.
Yes, the range should do this.
-Steve
