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
edited | 4k views
+3
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.
0

Normally enqueue is done at the tail, while dequeue is done at the head.

Normally, both these operations would take $O(1)$ time.

• For enqueue: attach a new node at the tail, then make the tail point to that node.

• For dequeue: Create a new pointer that points to head $\rightarrow$ next. Free the head. Then make head point to where the new pointer points.

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.

• To enqueue: Create a new pointer that points to the new node. Make the node point to the head. Now make head point to where the new pointer points. This is $O(1)$

• To dequeue: Create a new pointer that points to the second last node. Now, here's the catch. To reach the second last node, you'd have to start from the head, and traverse all the way around. This will take $\Theta(n)$ time. Now, make the tail point to this second last node, and delete off tail $\rightarrow$ next.

Option B

New node to be inserted is $P.$

Enqueue(){
P->Data=Data
}

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

Delete Tail

Dequeue(){
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 (61k points)
edited
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?
+7
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 ?
+2
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

0
Its singly linked list and not doubly therefore, dequeue will still be $\Theta(\mathrm n)$.
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)

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 (73 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.

Enqueue Time complexity will be O(1)

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