Deletion in Hash Table

1
votes

I was reading the book Introduction To Algorithms and I came across this:

We can delete an element in O(1) time if the lists are doubly linked. (Note that CHAINED-HASH-DELETE takes as input an element x and not its key k, so that we don’t have to search for x first. If the hash table supports deletion, then its linked lists should be doubly linked so that we can delete an item quickly. If the lists were only singly linked, then to delete element x, we would first have to find x in the list T[h(x.key)] so that we could update the next attribute of x’s predecessor. With singly linked lists, both deletion and searching would have the same asymptotic running times.)

How can we delete an element in O(1) time if the lists are double linked? First we will need to find the element and then we can delete it in O(1). But to find it we need O(length of the list) time. Maybe it's faster deleting in a doubly linked list (because we can search from the both ends of the list at the same time, but that is only constant improvement), but I don't see how it can be done in O(1) time.

Thank you in advance.

2
algorithmhash
Yeah, you're right that the doubly-linked list does not save much if one has kept a history of the prior link traversed. But it does at least save a second search if you haven't. And note this: "Note that CHAINED-HASH-DELETE takes as input an element x and not its key k". That indicates you're being passed just the element pointer, with no history. – Hot Licks
The implicit assumption in the quote is that the links are part of the elements, rather than there being a separate container-node object that implements the links and points to the element. In this way you don't have to search for anything to delete the element, you just use the FLink and BLink embedded in it. – RBarryYoung
In either the singly- or doubly-linked list, finding the element to delete is O(n). The actual deletion is O(1) in a doubly-linked list, or in a singly-linked list if you've kept track of the predecessor during the find stage (or if you play tricks like moving the next node data into the current node and deleting the next node instead). However, if you haven't tracked your predecessor node, and you don't move nodes, deletion in the singly-linked list is O(n) – twalberg
possible duplicate of Why deletion of elements of hash table using doubly-linked list is O(1)? – Want

2 Answers

4
votes

The answer is in the text;

Note that CHAINED-HASH-DELETE takes as input an element x and not its key k, so that we don’t have to search for x first.

You already have the item so you only have to remove it from the chain and do a delete.

To remove item X you need to get the previous and next node in the list and link them together before you delete X so the list remains unbroken. In a doubly linked list you already have a link to previous and next so this is constant. In a single linked list you would only have a link to next and so you need to scan through the list to find the previous node.

1
votes

I think the confusion here is because of the implicit assumption in CLRS. In this book, objects are often treated as property bags where required properties can be added at runtime - much like JavaScript but unlike Java/C# world. So if you want to put x in linked list, you don't necessarily need to create a Node object first and then add properties for Previous, Next and Value. Instead, you just add those properties to x itself. Many of us who have grown up with statically typed languages would be shocked at this design but for algorithm design with pseudo code, it removes unnecessary clutter. I think authors should have clarified this. In any case, without ability to add Previous, Next properties to object dynamically, yes, it would not be O(1) even with doubly linked lists.