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?
Normally enqueue is done at the tail, while dequeue is done at the head.
Normally, both these operations would take $O(1)$ time.
In this question, enqueue and dequeue are performed in a different manner. Enqueue is done at the head, and dequeue is done at the tail.
Option B
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$
What is mean by this line While(temp->Next->Next!=NULL)
Singly linked list you can't Travels reverse so creating temp pointer and forwarding until temp->next = tail, you can easy delefedelete the node
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
@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.