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?

+1 for posting a homework question with disclosure and showing that you've already tried something. Welcome to SO — JoshJordan, Jan 03 '10 at 19:28
The standard vanilla linked list will not give you O(1) search performance. — President James K. Polk, Jan 03 '10 at 19:29
@GregS - I've said I can return any element with the matching key, meaning I can just return the list's head, which is O(1). — CS n00b, Jan 03 '10 at 19:55
elements can have satellite data, what exactly does this mean? — Martin, Jan 03 '10 at 22:57
If it means that elements can have data attached to them, then you can attach a pointer back to the linked list node for the object, and delete becomes trivial — Martin, Jan 03 '10 at 22:58
If I store x',x'',x''' which have the same key in a linked list at T[key]. Why do you think that search can return any element, when I'm searching for only x''? — Rajat Saxena, May 24 '16 at 14:02
is there any different between `direct address table` and `hashtable` ? — roottraveller, Aug 17 '17 at 10:07

score 6 · Answer 1 · answered Jan 04 '10 at 19:16

6

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!

answered Jan 04 '10 at 19:16

Peter Hull

6,683
4
39
48

What if you have a list of n duplicate items? That will be O(n). – Mustehssun Iqbal Jul 14 '17 at 16:25
1

"Don't forget that Delete takes as an argument a pointer to an object to be deleted" - so you'll have a list of n-1 duplicate items. – Peter Hull Jul 15 '17 at 20:04
Got it. And in that case you wouldn't even need a doubly linked list. There is a method to delete the current node in O(1). Now not going to spoil the homework... – Mustehssun Iqbal Jul 17 '17 at 16:08

score 3 · Answer 2 · answered May 27 '14 at 08:04

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.

score 1 · Answer 3 · answered Jun 22 '12 at 09:12

I think you can make use of the satellite data to be mapped as a secondary key. Then it's a kind of 2-level hash table. Concerned with the DELETE operation, at first we use the primary key. And when there are duplicate primary keys, we use secondary keys to get the object. Therefore the total time is still O(1).

score 0 · Answer 4 · answered Jan 06 '13 at 10:30

The most important part.."implement a direct-access table in which the keys of stored elements do not need to be distinct" and " dictionary operation in O(1) time.

Insertion is also not possible in O(1) time if elements are equal(as Q says elements need not to be distinct).

For delete part you have to take keys as well as objects to reach to a particular object and assume an key out of satellite data too, to reach over a particular object.

I think only above 2 ideas make sense for O(1) time.

score 0 · Answer 5 · answered Jan 04 '10 at 02:01

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.

Implementing a direct address table

5 Answers5