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 (
SEARCH) should run in $\O(1)$ time. (Don't forget that
DELETEtakes as an argument a pointer to an object to be deleted, not a key).
Assuming that fetching an element should return the satellite data of all the stored elements, we can have each key map to a doubly linked list.
INSERTappends the element to the list in constant time
DELETEremoves the element from the linked list in constant time (the element contains pointers to the previous and next element)
SEARCHreturns the first element, which is a node in a linked list, in constant time