A queue is implemented using a non-circular singly linked list. The queue has…
GATE · 2018 · CS · Computer Science & IT
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 771 students.
Show answer
Correct answer: B
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2