GATE Computer Science (CS) 2018 Shift 1 Solved Paper

Question : 33 of 65

Marks: +1, -0

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and tail pointer, as shown in the figure. Let n denote of number of nodes in the queue. Let enqueue be implemented by interesting 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?

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

Validate

Solution:

For Enqueue operation, performs in constant amount of time (i.e.,

Θ(1)

) So, the options

B

is correct.

Go to Question:

Prev Question

Next Question