GATE CS 2017 Set 2 Q13 — Arrays, Stacks and Queues

In a circular queue implemented using a singly linked list, the elements are ordered from FRONT to REAR. To maintain circularity, the last node (REAR) must point back to the first node (FRONT). Thus, Statement II is correct.

Let's analyze the operations under this configuration:

• Deletion (Dequeue): To delete from the front, we update FRONT to point to the next node (i.e., FRONT = FRONT->next) and update the REAR->next pointer to the new FRONT. This takes $\mathcal{O}(1)$ time. If Statement I were true (i.e., FRONT->next pointed to REAR), we would lose the link to the second node in the queue, making deletion of the front node impossible in $\mathcal{O}(1)$ time for queues of size greater than 2.
• Insertion (Enqueue): To insert a new node N at the rear, we set N->next = REAR->next (which is FRONT), then update REAR->next = N, and finally set REAR = N. This also takes $\mathcal{O}(1)$ time.

Hence, only Statement II is correct, making B the correct option.