A circularly linked list is used to represent a Queue. A single variable p is…
2004
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.
front node
- C.
not possible with a single pointer
- D.
node next to front
Attempted by 441 students.
Show answer & explanation
Correct answer: A
Answer: Point p to the rear node (the last node).
Why this works:
Representation: In a circular singly linked list the node after the rear is the front (rear->next is front). Having p point to the rear gives direct access to both rear and front.
Enqueue (insert at rear): Create new node new. Set new->next = p->next (current front). Set p->next = new. Update p = new so p again points to the rear. All are constant-time pointer updates.
Dequeue (remove from front): Let front = p->next. If front == p (single-node), remove it and set p = null. Otherwise set p->next = front->next and free front. These are constant-time pointer updates.
Empty and single-node cases: Represent an empty queue by p = null. After the first insertion set p to the new node and new->next = new (self-loop). Removing the last node sets p back to null.
Time complexity: Both enqueue and dequeue are O(1) because they perform a fixed number of pointer updates without traversal.