Exercise 11.1.3

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

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.