GATE2017-2,circular Queue implemented by single linked list

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)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).

shivani @shivani1234
27 May 2017 01:20 am
  • b is correct , to verify it just take example like 2(f)->7->9->1(r), consider circular linked list next of 1 is 2 , if you place pointer on next of front node(2) then to reach 1 (last node) , you have to traverse complete list.,or for delete O(1) and insert O(n).
  • while , if u place ptr next to rear (1) then to reach (2 )you can do in O(1) time, or for insert it takes O(1) and delete it takes O(1) as next of rear is front node as list is circular here.
shweta @shweta1920
1 Jun 2017 05:41 am

thank you @shivani1234