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 enQueue and deQueue can be performed in constant time?

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

Answer 1

The correct option is B not possible with a single pointer



To add a new node:


new$\to$ next = Rear $\to$ next;
Rear$\to$ next = new;
Rear = new;


It will take constant time.

Similarly delete node from Front node will be:

Front = Rear $\to$ next;
Rear $\to$ next = Front $\to$ next;
free (Front);

It will also take constant time.