GATE CS 2004 Q36 — Linked Lists

To represent a Queue using a circularly linked list with a single pointer $p$ in $O(1)$ time for both enQueue and deQueue, the pointer $p$ must point to the rear node.

Analysis of Options:

1. If $p$ points to the rear node (Option A):
   • Front Node: Can be accessed directly in $O(1)$ time as p->next.
   • deQueue (Deletion from Front):
     The front node is p->next. To delete it, we update the rear's next pointer:
     p->next = p->next->next;
     This takes $O(1)$ time.
   • enQueue (Insertion at Rear):
     To insert a new node temp at the rear:
     temp->next = p->next; (point new node to front)
     p->next = temp; (point old rear to new node)
     p = temp; (update $p$ to point to the new rear)
     This takes $O(1)$ time.
2. If $p$ points to the front node (Option B):
   • To perform enQueue, we need to insert at the rear. Finding the rear node requires traversing the entire list from the front, which takes $O(n)$ time.

Thus, pointing to the rear node allows both operations to be completed in $O(1)$ constant time.