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. 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?

Thanks!

Answer 1

Hash tables will work for you up to a certain point. Once you start having collsions, then it becomes O(1+k/n) where k is the number of keys and n is your table size. If you do a scheduled hash resize and re-hash, then you might be able to get away with this. Don't know if that would affect your efficiency rating since it doesn't happen during insertion, deletion or search.

Deletion by not changing the object can be achieved by simply setting the hash reference pointer to null. No direct change to the object is made, but changes to the object container are made.

I think for most of the restrictions that you are giving, a hash table can be implemented in certain ways to get around them. There is more information at http://en.wikipedia.org/wiki/Hash_table#Performance_analysis on how to implement a hash table.

Answer 2

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 3

For the deletion you can store the linked list as doubly linked list to avoid traversing the whole linked list for deletion of the node.