Perhaps I need to re-review the analysis of CLR-1990*, because they clearly
state on page 223:
The worst-case running time for insertion is O(1). For searching, the
worst-case running time is proportional to the length of the list: we
shall analyze this more closely below. Deletion of an element x can be
accomplished in O(1) time if the lists are doubly linked.
Note, I wasn't referring to perl's hashes in particular, just hashes in
general.
* Cormen, Leiserson, Rivest 1990: Introduction to Algorithms. MIT Press,
Cambridge Massachusetts.
| [reply] |

*Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked.*
It still means you need to find an object before you can delete it.
| [reply] |

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*.
Abigail
| [reply] |