in reply to
Re: Re: A short meditation about hash search performance
in thread A short meditation about hash search performance
If you read page 223 carefully, you see that the arguments
to the function Chained-Hash-Delete are
(T, x) and not (T, k). Now x is
here the node to be deleted. That is, you have already found the node with key k to be deleted.
So, yes, for a double linked list, the actual deletion is
in constant time, but that does not include the time to
search for the node to be deleted.