GATE CSE 2018 | Question: 3

Question

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let $n$ denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of 'enqueue' and 'dequeue, respectively, for this data structure?

• A. $\Theta(1), \Theta(1)$
• B. $\Theta(1), \Theta(n)$
• C. $\Theta(n), \Theta(1)$
• D. $\Theta(n), \Theta(n)$

Comments

Even for the Circular Singly Linked List answer would be option (b) only.

---

@Abhishek124 Tiwari nope. for circular singly linked list we can do both enqueue and dequeue operation in Θ(1) time. read the question.

---

we have to free the node after dequeing(deleting) it and point the preceding node to null

we couldn't do that until we have the pointer to preceding node , for that we may want to transverse from the start

resulting in  O(n)

cheers :)

Answer 1

Answer is B:

 In question there is a Single linked list of n nodes which is given. In this Linked list backward traversing is not possible. and the queue is FIFO data structure.

1)For  Enqueue:This will take θ(1) because inserting a new node at the head(first node) will take constant time.

1)For  Dequeue: In queue deletion of first inserted element, it will take θ(n) time to trace the path from the last node to the first node for deletion

 

 

 

Comments

@Viplav Patil

In your case 2nd for Dequeue:- I think it is mentioned thereself in the question that 'dequeue' can be implemented by deletion of a node from the tail.

But you mention that "it will take θ(n) time to trace the path from the last node to the first node for deletion" which is wrong.

It should be like "it will take θ(n) time to trace the path from the first node to the last node for deletion" as we are implementing it by non-circular singly linked list.

Answer 2

It is (B) if we use simple Linked List, and constant time if a doubly Linked List would have been given.