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

[John Surcombe]

From: "M.Y.W.Y.B." <mywyb2@hermes.cam.ac.uk>

> --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])].

Yes, but finding the item is a separate operation from deleting it.  Finding
the item means finding a pointer to an item given some value known to be
attributed to that item, and can only be achieved by looking at every item
and comparing the values - deleting an item in this case assumes you already
have a pointer to the item to delete.  For example, if I asked for a routine
to be written to delete every other item in a doubly linked list then this
can be done in O(n) time, because it involves O(n) delete operations each
taking O(1) time.

Cheers now,
John