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

[Leo Dearden]

Leo Dearden wrote:
> 
> p223, last paragraph.
> 
> 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.

I'd better clarify. 

	A number of people have pointed out that, given only a pointer to an
item in a doubly linked list, that item _can_ be deleted in O(1), where,
as stated in the book that isn't possible with a singly linked list. I
understood and acepted that. 
	My question arose because, in the context, a chain-on-collision
hashtable, I couldn't see how that pointer could be obtained in less
than O(n). The entire process of deletion of the item from the list (and
thus from the hashtable) had thus to be at least O(n), whereas the
paragraph in question asserts that it can be done in O(1). 

I think that we have established that:
	*If you have a pointer to an object in a DLList deletion of that 
object is O(1).
	*Searching such a list for a particular item is O(n).

I posted to see if I was missing some subtlety of the behavior of the
hastable or DDlists in general. I'm now satisfied that I wasn't, and
I'll try to be clearer as to what I'm looking for in future.

L.