Suggest a data structure for representing a subset $S$ of integers from $1$ to $n$. Following operations on the set $S$ are to be performed in constant time (independent of cardinality of $S$).
i. MEMBER $(X)$:
iii. ADD $(X)$:
iv. DELETE $(X)$:
Give pictorial examples of your data structure. Give routines for these operations in an English like language. You may assume that the data structure has been suitable initialized. Clearly state your assumptions regarding initialization.
A queue with a hashtable.
Intialize hashtable with $0$.
When inserting $X$ into the queue update $hashtable[X]=0$ to $hashtable[X]=1$.
In case of array or only a hash table,
how can we ensure part(ii) in constant time, because checking all slots in array or hash table to determine if it is empty or not will take O(n) time.
I think queue + hash table(or array) both needed.
'Sourav Basu :- But what if that lastelement is deleted .
@ rahul sharma 5
if last element is deleted, then array and queue both will be empty.
@ Sourav Basu
Here delete and add can be done constant time by a queue
and Find-one and member operation can be done in constant time in a hash table
That is why queue and hash table both needed here
By using queue ,we are restricting to deletion from front only.Delete(X) should delete X,no matter whether it is front of queue or not,X should be deleted.So,using queue it cannot be handled.See my answer below,i tried with DLL
We should use Hashing+ Doubly linked List. Let us say H is my hash table and each entry in hash table will either has NULL or it has the node address in which X is stored.Doubly linked list will have a head pointing to first node.We will do insertion at head always.
(i). MEMBER (X):
Please let me know if anything is wrong