A queue is implemented using a non-circular singly linked list. The queue has…

PYQ GATE 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 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 897 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…