GSoC-2011 project:: Containers

[spir]

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