The Gateway to Computer Science Excellence
+15 votes
3.4k views

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?

  1. $\Theta(1), \Theta(1)$
  2. $\Theta(1), \Theta(n)$
  3. $\Theta(n), \Theta(1)$
  4. $\Theta(n), \Theta(n)$
in DS by Boss (16.6k points)
edited by | 3.4k views
+2
The important point here is that you need the second last node address for the tail pointer to point to after deleting the last node, so while dequeuing you need to traverse the list and keep track of whether you have reached the 2nd last node.
+1
Either we enqueue or dequeue we need to maintain the head and tail ponter.

So for enqueue we simply changes the head pointer to newly inserted node in O(1) but for dequeue we have to point tail pointer to the second last node, since it is singly linked we doesn't have address of previous nodes so we need to traverse linked list upto that node and then perform deletion(pointing tail to second last node & free last node) which in worst case can take O(n) time.

4 Answers

+23 votes
Best answer

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$

by Veteran (60.4k points)
edited by
0
but since the tail pointer is maintained can't we directly access the last node using the tail pointer?
0
Since tail is already pointing to the last element of the linked list? Why do we need to traverse the linked list?
+6
tail pointer is maintained, i agree, but to get the address of second last node, you need to traverse the list. That's why, to delete a node, complexity is O(n)
0
What is mean by this line   While(temp->Next->Next!=NULL)
+1
It means you are applying while loop till you reach the 2nd last element
0
How can we calculate average case time complexity ? Is most of the time average case time complexity same as worst case time complexity ?
+1
Even if one argue that pointer "tail" is given so that we can directly delete it, what about second dequeue. Once you do free(tail), you don't have access to second last node. Either you keep track of second last node or just delete the node pointed by tail, it will take n-1 traversal to reach second last node. hence theta(n).
0

Singly linked list you can't Travels reverse so creating temp pointer and forwarding until temp->next = tail, you can easy delefedelete the node 

+5 votes
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)
by (115 points)
0 votes

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

 

 

 

by (79 points)
0

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

0 votes
Enqueue Time complexity will be O(1)

Dequeue Time Complexity will be O(n)
by (43 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,136 answers
193,697 comments
93,478 users