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.

• INSERT appends the element to the list in constant time
• DELETE removes the element from the linked list in constant time (the element contains pointers to the previous and next element)
• SEARCH returns the first element, which is a node in a linked list, in constant time