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?
Please tell me if my understanding is correct: each slot in T[0,1,2….m-1] is storing (1) a flag (2) an element (3) 2 pointers
So, instead of the slot T(h(k)) being a pointer to a list, it is able to save one element and then that element points to a list
There is also a “free list”
There is only one flag for each slot T[0,1,2….m-1]
To insert an element ‘x’ we will first check T[h(x.key)] to see if it is free. If it is free then we insert T[h(x.key)] and change the flag = 1
If it was not free, then there is a list, so we insert it at the beginning of the list
To delete we will check x.prev and x.next to see if they are NULL. So when we delete the element ‘x’ we will be left with an empty list at that slot. So we insert T[h(x.key)] into the free list and update the flag to 0 and then delete the element x from the list its stores in
What I don’t understand is the functionality of maintaining a free list?
Is there a single free list for the whole hash table or does each slot have its own free list?
Also why insert the element to be deleted into the free list and then delete it? Why don’t just delete it without using the intermediate free list?
I am unable to visualize the use of the free list as mentioned in the question.