8.5k views

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?

1. Next pointer of front node points to the rear node.
2. Next pointer of rear node points to the front node.
1. (I) only.
2. (II) only.
3. Both (I) and (II).
4. Neither (I) nor (II).
in DS
edited | 8.5k views
+1
Since linked list is a dynamic data structure we don't need to worry about efficient space utilization (as we do in case of implementing circular queue using array). We can perform both enqueue and dequeue in constant time by using only front and rear pointers. Simply the next pointer of rear node points to NULL and next pointer of front node points to the node which was inserted just after front node in the  queue (i.e second element from left in the list). Enqueue is done at rear and dequeue is done from front ,both in constant time. So both options are false.  D should be the answer.
0
According to yr explanation option A should be same then ,why are u going for option D
0
Can anyone explain this question pictorially, so that I can visualize the concept of the question.
0
As insertion takes place from the rear side, so the next node to rear must point to the front node, to be a circular queue. I think this is the logic in simple terms.
+3