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

Okay in this question a linked list is used and time complexity for dequeue is o(n) because we need pointer to the last element which we will get from 2nd last element, but what if its just a simple queue? Than the operation of deque will have 0(1) time complexity?

---

After deleting the last node using tail pointer, then  we need to point that pointer to the node prev to it for that reason we can't perform it in O(1)

---

yes, to delete tail, we must traverse from head to find the node just before tail. 

Answer 1

New node to be inserted is $P.$

Enqueue(){
    P->Data=Data
    P->Next=Head
    Head=P
}

Time Complexity $=O(1)$ Because only pointer manipulation is involved which takes constant time.

Delete Tail

Dequeue(){
    temp=head
    While(temp->Next->Next!=NULL)
         temp=temp->next
    temp->next=NULL
    tail=temp
}

Time Complexity = Time for Traversing list, free the last node and keep track of Tail pointer $= O(n)$

Answer is $B$

Comments

@Balasubramani A We can't delete the last node directly as we don't know the address of the second last node (where our TAIL would point to after deletion). We need to traverse to the second last node as such:

 

// Dequeue

Node *second_last = head;

// Move `second_last` to the second last node
while (second_last->next->next) {
    second_last = second_last->next;
}

Node *target = second_last->next; // `target` is the last node in LL
second_last->next = NULL;
tail = second_last;

return target;

Which would be O(n).

If the queue was implemented using a double linked list, deletion would take O(1) since we can directly access the second last element as second_last = last->prev;

---

SInce Queue follows LIFO order so shouldn't  deletion be from head node and enqueue from tail?

---

Queue follows a FIFO order, not LIFO.

Answer 2

Even if we have the pointer to the tail of the list, in oder to delete it, we need the address of the 2nd last node which can be obtained by traversing the list. so theta(n).

Ans. is (B)

Answer 3

Enqueue will take O(1)

Algorithm

1. temp = head
2. head = head -> next
3. free(temp)

Dequeue will take O(n)

Algorithm:

1. Traverse to pre tail node and store its address in pre_tail       ............. O(n)
2. temp = tail
3. tail = pre_tail
4. free(temp)

Comments

I think you are confused between the meanings of Enqueue and Dequeue

Answer 4

Enqueue Time complexity will be O(1)

Dequeue Time Complexity will be O(n)

Answer 5

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 6

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