On Mar 31, 11 02:30, spir 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.
Denis
Using 'previous' pointer to allow O(1) removal will make this program
crash, although I don't know if this is allowed or not:
auto r = slist.front;
r.popFront();
slist.removeFront();
slist.remove(r);
(You don't need 'next' because it is already stored in the 'current' node.)
