Suggest how to implement a direct-address 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)

Since the keys are no longer distinct, our implementation needs to somehow keep track of how many times a particular key exists using satellite data. One way we could do this is by having each key correspond to a doubly-linked list of length \(n\) where \(n\) is the number of times that key is stored. Unused keys would hold a \(NIL\) value.

SEARCH(T, k) would simply return the first element of the doubly-linked list in slot \(k\) if there is one and \(NIL\) if there isn’t.

INSERT(T, x) would then either establish a single-element doubly-linked list in slot \(x.key\) or append another node to the existing doubly-linked list in that slot. In order to maintain constant time with this operation, we should insert the new node to the head of the doubly-linked list since the order of elements is irrelevant.

DELETE(T, x) supplies us with a pointer to the node that we want to remove from its doubly-linked list. This can be done in constant time by simply relinking its neighbors within the list.