Implementing a direct address table

Question

I was given as homework the Introduction to Algorithms exercise 11.1-3 which goes as follows:

Suggest how to implement a direct-access table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations (Insert, Delete and Search) should run in O(1) time. Don't forget that Delete takes as an argument a pointer to an object to be deleted, not a key.

Well, Insert is no problem, as it simply means creating a linked list at the appropriate place in the table (if it doesn't already exist) and adding the element to it. Search, which is given a key, can return any of the elements that match the key, so it simply means we need to return the head of the matching list in the table.

My problem is with Delete operation. If I modify the object to add to it a pointer to its node in the linked list, then I can delete in O(1), but I'm not sure I'm allowed to change the object. Is there a way for doing this without changing the given object?

Answer 1

Is this a question from the Cormen book? As I understand it, from reading the previous paragraphs in that book, the object that you store in the direct access table is 'your' object. So you can, as you suggest, store pointers to doubly-linked lists in the table with each list element having a pointer to the user's object. Then, the dictionary SEARCH operation returns a list element and the user must use a further step to get at his object. Likewise the DELETE operation takes a pointer to a list element.

Does that make sense? I don't want to spoil your homework!

Answer 2

We can use a double linked -list at every indices of direct-address table. Slot j will contain a pointer to the head of the list, which contain all the elements with key-value j and if there are no such element slot j contains NIL. INSERT-inserting x at the head of the list will take just O(1) time. SEARCH- It can return any element that matches the given key and thus returning the head of the list will just take O(1) time. DELETE- As we have used double linked-list, we can delete an element in O(1) time using pointer to previous and next nodes.