GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 34

Question

Suppose you implement a queue using a singly linked list with head and tail pointers so that the front of the queue is at the tail of the list, and the rear of the queue is at the head of the list.

What is the best possible worst-case running time for enqueue and dequeue in this situation? (As a reminder, enqueue occurs at the rear of the queue.)

• A. $O(1)$ for both functions.
• B. $O(1)$ for enqueue and $O(n)$ for dequeue.
• C. $O(n)$ for enqueue and $O(1)$ for dequeue.
• D. $O(n)$ for both functions.

Answer 1

In the time of enqueuing we are using tail pointer to direct insert the node in rear

so it takes O(1) in worst .

But in the time if dequeuing we are traversing that tail pointer to the first node where head already exists..so now to delete or dequeue the element we need to traverse tail pointer to whole SLL to get that front pointer node in queue. SO O(n) in worst case.