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 nn denote the number of nodes in the queue. Let enqueueenqueue be implemented by inserting a new node at the head, and dequeuedequeue 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 enqueueenqueue  and dequeuedequeue , respectively, for this data structure?

  1. A.

    θ(1),θ(1)θ(1), θ(1)

  2. B.

    θ(1),θ(n)θ(1), θ(n)

  3. C.

    θ(n),θ(1) θ(n), θ(1)

  4. D.

    θ(n),θ(n)θ(n), θ(n)

Attempted by 807 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…