Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in \(O(1)\) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?

Have each slot of the table \(T\) hold a flag of \(1\) if there is a value in that element and \(0\) if it is free. To maintain the required runtime, our free list must be doubly linked.

• Searching is still the same having an expected run time of \(O(1)\).

• Inserting works by checking to see if \(T[h(x.key)]\) is free. If it is, replace \(T[h(x.key)]\) with the new value and a flag set to \(1\). If it wasn’t free then we append the inserted value onto the list that is already there. Either possibility runs in \(O(1)\) time.

• To Delete, if the element being deleted has \(NIL\) values in its \(next\) and \(prev\) attributes (since it is coming from a doubly-linked list) then we manage the table data at position \(T[h(x.key)]\) by replacing it with a flag of \(0\) indicating that the slot is now free. Otherwise we remove it from its position in the doubly-linked list for data at that hash table point. Either operation runs in \(O(1)\) time.