\text{FIND-ONE $(S):$} & \text{If $S$ is not empty, return one element of the set $S$}\\ & & \quad\text{(any arbitrary element will do)} \\ \text{iii.} & \text{ADD $(X):$} & \text{Add integer $X$ to set $S$} \\ \text{ii.} & \text{DELETE $(X):$} & \text{Delete integer $X$ from $S$} \end{array}$$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.

### 6 Comments

prithatiti Direct address tables use arrays which are random access data structure, so, the key values (which are also the index of the array) can be easily used to search the records in O(1) time.

## 2 Answers

A queue with a hashtable.

Intialize hashtable with $0$.

When inserting $X$ into the queue update $hashtable[X]=0$ to $hashtable[X]=1$.

- If $hashtable[X]=1$ then return true.
- Return the element at the front or rear of the queue.
- Add the element $X$ to the queue at the rear end and update $hashtable[X]=0$ to $hashtable[X]=1$.
- Delete the element $X$ from the front end of the queue and update $hashtable[X]=1$ to $hashtable[X]=0$.

### 15 Comments

X can be at any arbitrary position so how point (iv) is true???

we can always make hash[X] = 0 but it will not always be present on front node

@ srestha

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

I am also having the same doubt that if **queue** is used with the** hashtable** then how the last point will satisfy .As we will have two cases here.

**CASE 1**: if the element X is inserted and it is the only element in the queue then when we perfrom delete (X) then that element will get deleted in constant time.

**CASE 2**: if before inserting the element X there are some more elements in the queue then if we want to delete x for that we have to perform so many deletions __(as in queue deletion will be done from the front always) __. here in worst case it will take

**O(n)**.

**[considering n elements in the queue].**i have doubt in **case 2**..is this case even possible ? or we should only consider the** CASE 1**__. (initially empty queue)__

someone please clarify this !!

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): |
Goto H(X) and see if it is NULL or not.If NULL,then return false else true |

(ii). FIND-ONE(S): | Return front node from linked list. |

(iii). ADD (X): | Create a new node and store the address in the H(X).And then make this node as a head of linked list |

(iv). DELETE (X): | Goto H(X),Take the address of the node and set the prev and next nodes pointer in constant time and free the current node by marking H(X) as NULL. |

Please let me know if anything is wrong

### 4 Comments

The problem with the selected answer is that it is using queue and from queue you can delete the intermediate nodes.And it can be the case that X element is lying in the middle of the queue which will not be deleted.