A circular queue has been implemented using a singly linked list where each…
2017
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in \(O(1)\) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
- A.
(I) only
- B.
(II) only
- C.
Both (I) and (II)
- D.
Neither (I) nor (II)
Attempted by 288 students.
Show answer & explanation
Correct answer: B
Answer: The next pointer of the rear node should point to the front node (rear.next = front).
Why this is required:
Insertion (enqueue) O(1): Link the new node after rear, update rear to the new node, and set rear.next = front. For an empty queue set front = rear = new node and rear.next = front.
Deletion (dequeue) O(1): Move front to front.next and then set rear.next = front to preserve circularity. If the queue becomes empty set front = rear = null.
Why the front node's next pointer should not point to the rear node:
In general, front.next should point to the second element of the queue. Making front.next = rear would only hold in the special case of a two-element queue and is not a correct general property.
A video solution is available for this question — log in and enroll to watch it.