edited by
27,154 views
35 votes
35 votes

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

11 Answers

Best answer
22 votes
22 votes

Reference: https://gateoverflow.in/1033/gate2004-36

This is how the things look.

We do insertion by cutting in between Rear and Front and we do deletion by forwarding the Front pointer and updating the Rear accordingly.

Correct Answer: $B$

edited by
27 votes
27 votes

Answer is Next pointer to Rear node has Pointer to Front node.

Hence, only (II) is correct.

12 votes
12 votes

Answer B

for circular queue using single link list, for enqueue and dequeue operation in O(1) time rear->next should point front

When you create a new node then there should be a pointer which points that newly created node . This pointer is necessary.

For enqueue

pointer->next = rear->next

rear->next=pointer

rear=pointer

 It takes O(1) times

For dequeue

rear->next = front->next

pointer=front ( this extra pointer required to    free the memory  deleted node)

front= rear->next

Free(pointer)

It takes O(1) times

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

http://googleweblight.com/i?u=http://btechsmartclass.com/DS/U2_T9.html&grqid=wV00kE3q&hl=en-IN
edited by
Answer:

Related questions