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

[M.Y.W.Y.B.]

--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