A circular linked list is used to represent a queue. A single variable ‘P’ is…
2022
A circular linked list is used to represent a queue. A single variable ‘P’ is used to access the queue. To which node should ‘P’ point so that both enqueue and dequeue operations can be performed in constant time?
- A.
rear node
- B.
front node
- C.
not possible with single pointer
- D.
node next to front
Attempted by 661 students.
Show answer & explanation
Correct answer: A
Key idea: keep P pointing to the rear node of the circular linked list.
Then front = P -> next; rear = P.
Enqueue requires quick access to the rear.
Dequeue requires quick access to the front.
Enqueue (insert element x):
If P == NULL (queue is empty): create new node; set new.next = new; set P = new.
Else: create new node; set new.next = P.next; set P.next = new; set P = new.
Dequeue (remove front element):
If P == NULL: queue is empty (underflow).
Let front = P.next.
If front == P (only one node): set P = NULL.
Else: set P.next = front.next (unlink front). Return front's value.
Because each operation uses a fixed number of pointer updates (and no traversal), both enqueue and dequeue run in O(1) time.