The GATE Grind

GATE 2018 CS – Question 13

Programming and Data Structures · Stacks and Queues · 1 mark · Multiple choice

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?

Diagram for GATE 2018 CS question 13
  1. $\theta(1),\theta(1)$
  2. $\theta(1),\theta(n)$
  3. $\theta(n),\theta(1)$
  4. $\theta(n),\theta(n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\theta(1),\theta(n)$

Explanation

Inserting at the head of a singly linked list takes $\theta(1)$. Deleting at the tail needs the predecessor of the tail node, and with only forward links that means traversing the list, which is $\theta(n)$.