GATE CSE 2017 Set 2 | Question: 13

Question

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

I feel whatever be the order of the rear and front pointer it doesnt matter .....it will be O(1) for deletion and insertion

But the key says only B is right

would be helpful if someone explains this one

Comments

Why will you consider the first option?It can become true while doing enqeu dequeue operations on quue when we have only one element left,the front and rear both point to the first node.Incase queue is empty both will be NULL.

And the first condition need not hold always.And neither it is a property of circular queue nor a required condtion to implement circular queue

---

got it :)

---

$\mathrm{REAR}\to \mathrm{next}=\mathrm{FRONT}$ makes the circular queue as it is singly linked list and the insertion and deletion will take place in REAR and FRONT respectively.

BTW you took $\mathrm{FRONT}\to \mathrm{next}=\mathrm{REAR}$, the reverse linked list would be created i.e. Insertion and Deletion would take place in FRONT and REAR respectively.

Answer 1

for option (i) if front ->rear then

 for insert a new node can take o(1): because new->=rear-> and rear->=new

but for delete a node from list: we find out a node which pointing the node front then from that node next=front-> then delete front which take o(n) time to find the node which next is fron.