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

[Isabel Kingsmill]

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

>
> implies that deletion of an item from a doubly (but not singly) linked
> list can be accomplished in O(1). Don't you still have to find the item
> in the list before you can delete it (taking O(n)), regardless of the
> linking?
> Thus the whole operation takes O(n) regardless of linking.
>
>
> _______________________________________________
> CST-1B mailing list
> CST-1B@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-1b
>