retagged by
15,223 views
36 votes
36 votes

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)$
retagged by

6 Answers

Best answer
43 votes
43 votes

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$

edited by
6 votes
6 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)
3 votes
3 votes

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)
edited by
Answer:

Related questions