[Cst-1b] Introduction to Algorithms (CLR).

[Martin Harper]

"M.Y.W.Y.B." wrote:

> --On Sonntag, 7. Mai 2000, 13:52 +0100 "Isabel Kingsmill" <iek20@cam.ac.uk>
> wrote:
>
> > I think the point is that you know which element you want to remove, so
> the
> > amount of work needed to remove it is constant as it only involves dealing
> > with the elements on either side of it (because it is doubly linked).
> But,
> > if it were a singly linked list then as you don't have a pointer to its
> > predecessor, you have to step through the entire list in order to find the
> > predecessor before being able to make the necessary alterations to it
> which
> > makes the amount of work needed O(n).
> >
> > Isabel
>
> But even if you've got a doubly linked list you first have to find the item
> x before you can delete it. I can't see how you can do that in time less
> than proportional to the length of the list T[h(key[x])].
> Moritz

A) Use of an iterator.
B) Use of the GC (with a softly linked list).
C) Cache most recently accessed element in some structure.
D) Pass elements around your program (by reference ;). for a while, until they
are finally deleted.

The last example is perhaps the most persuasive - you may have the deletion
happening in a seperate part of the program to the finding. Heck, it could be on
a seperate thread, or even a seperate computer! For all these reasons, the time
taken *just* to delete an element is important, and it's faster in a doubly
linked list...

Martin.