A queue is implemented using a non-circular singly linked list. The queue has…
2018
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?
- A.
\(θ(1), θ(1)\) - B.
\(θ(1), θ(n)\) - C.
\( θ(n), θ(1) \) - D.
\(θ(n), θ(n)\)
Attempted by 490 students.
Show answer & explanation
Correct answer: B
Answer: θ(1) for enqueue, θ(n) for dequeue.
Why enqueue is Θ(1):
To enqueue, create a new node, set its next to the current head, and update the head pointer.
These are fixed-number pointer updates, so the operation takes constant time Θ(1).
Why dequeue is Θ(n):
To delete the tail node you must update the next pointer of the node just before the tail (the predecessor).
A singly linked list does not provide a direct pointer to the predecessor of the tail, so you must traverse from the head to find it, which takes Θ(n) time for n nodes.
A video solution is available for this question — log in and enroll to watch it.