GO Classes DPP | GATE CS | Data Structures | Circular Linked List Queue

Answer 1

If $\text{Q}$ points to the rear node, then:

front node = Q->next
rear node  = Q

Enqueue can be done after the rear node in $\text{O}(1)$ time.

Dequeue can remove $\text{Q} \rightarrow \text{next}$, which is the front node, also in $\text{O}(1)$ time.

If $\text{Q}$ points to the front node, then reaching the rear node may require traversal.

So the better design is to keep $\text{Q}$ pointing to the rear node.

Correct option: B

Answer 2

Say the queue currently has 10, 20, 30 (10 is front, 30 is rear).

Enqueue(40) add 40 to the rear
newNode(40)->next = Q->next(10)
Q->next(30's next) = newNode(40)
Q = newNode // now rear at 40
now 10-20-30-40-10 ...In O(1)
  
Dequeue(10)

temp = q.next // store 10
q.next = q.next.next // rear next is to 20
temp.next = null;

now 20-30-40-20..In (O(1))
As both the enque and deque is done in O(1) , what exactly is done in normal queue..so it's the best Design..

Answer 3

Design 1: Q points to the node containing the front item. Then inserting into the rear would take linear time, having to scan through all the elements to find the rear node with repeated $curr\to next == Q$, then we can insert in the rear.

Design 2: Q points to the node containing the rear item. Then insert rear is simple, and to get front, we just have to look at the next element, and removing it also would be easier since the rear element is the previous element of the front element.

Answer: B