GATE CSE 2004 | Question: 36

Question

A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

• A. rear node
• B. front node
• C. not possible with a single pointer
• D. node next to front

Comments

A circular linked list given, meaning the last address of linked list will point to head or start of linked list. Also this implementation is of a queue.

Now from the diagram, rear and front are given, which means following queue property first in first out we are deleting from front and as the queue grows we are adding to rear.

Say, first 2 enters in the linked list.

Then 3 and then 5 and then 6 enters.

Now according to question,

The linked list will look like

2->3->5->6 (6 is rear latest added and 2 is front oldest added)

And since circular linked list is used  6 points to 2.

 

Now where to point the pointer p such that insertion and deletion takes constant time.

 

Clearly if we point it to front, then deletion is constant time but not the insertion as we need to travel the whole linked list it's n time.

 

But if we point to rear then insertion takes constant time as p is pointing to rear element. And deletion is also constant time as rear points to front so we can go to front directly.

Therefore, the p points to rear.

---

$$
\begin{aligned}
\textbf{P points to Rear:} & \quad \text{It is the same as having a rear pointer; P simply acts as an additional pointer to the rear node.} \\[6pt]
\textbf{P points to Front:} & \quad \text{If P points to the front and we perform a dequeue, the front moves to the next node.} \\
                           & \quad \text{The old front node gets deleted, but P still points to that deleted node,} \\
                           & \quad \text{so P becomes a dangling pointer.}\\

\end{aligned}
$$
correct me, if i am wrong?

---

@duckduck if P points to front, then it takes O(n) to make rear point to the node next to front so it is not correct answer.

Answer 1

I think there is no front or rear pointer here only p pointer so enQueue() and deQueue operation should be this

1.) newNode-->next=p-->next-->next;

2.) p-->next-->next=NULL;

3.) free(p-->next);

4.) p-->next=newNode;

Comments

@One

yes u r right they were not mentioned about rear and front pointers they only give us pointer P