CODEWITHSUNDEEP
algorithmhash
Want
Want

Reputation: 820

Deletion in Hash Table

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.

Upvotes: 1

Views: 1866

Answers (2)

Shital Shah
Shital Shah

Reputation: 68728

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.

Upvotes: 1

Jonathan Pierce
Jonathan Pierce

Reputation: 184

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.

Upvotes: 4

Related Questions