IAE Academy

GATE 2018 CS Q.3: solution and answer

GATE 2018 · CSQ.3 · 1 mark · MCQ

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 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.

[Figure: a singly linked list of nodes drawn left to right, each node a two-cell box with a right-pointing arrow to the next node. The first (leftmost) node is labelled by an upward arrow from the word "head". A row of dots indicates further nodes in between. The last (rightmost) node is labelled by an upward arrow from the word "tail", and its next-pointer cell points to a ground symbol (null terminator).]

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

GATE 2018 CS question 3: A non-circular singly linked list drawn left to right: each node is a box split into a data cell and a next-pointer cell…Tap to open full size
Figure from the GATE 2018 CS paper. It is part of the question.
Figure description

A non-circular singly linked list drawn left to right: each node is a box split into a data cell and a next-pointer cell, with an arrow from the pointer cell to the next node's box. The head pointer points (upward arrow) to the first node. A row of dots between the second node and the last node indicates additional nodes. The tail pointer points (upward arrow) to the last node, whose next-pointer cell points to a ground/earth symbol representing NULL — confirming the list is singly linked (no backward links) and non-circular.

  1. (A)

  2. (B)

  3. (C)

  4. (D)

Answer and solution

ANSWER

Θ(1), Θ(n) — option (B)

Official answer: BSource: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. enqueue inserts a new node at the head: allocate the node, set its next pointer to the current head, then update the head pointer to the new node. Every one of these operations is constant-time regardless of n, so enqueue is Θ(1).

  2. dequeue deletes the node at the tail. After deletion, the new tail must be the node whose next field currently points to the (old) tail node.

  3. In a singly linked list, links only go forward (head → ... → tail); there is no pointer from the tail back to its predecessor.

  4. The only way to find the predecessor of the tail is to start at head and walk forward, checking node->next == tail at each step, until it is found. This visits up to n−1 nodes, so it costs Θ(n).

  5. A separate tail pointer does not help here: it gives direct access to the last node itself, but not to the node before it, since no backward links exist.

  6. Hence the most time-efficient dequeue still requires Θ(n), giving the pair (Θ(1), Θ(n)) — option (B).

KEY IDEA

In a singly linked list only forward (next) pointers exist. Inserting at the head is always O(1). Deleting at the tail needs the new tail (the second-to-last node), and the only way to find it is to traverse from head, which is O(n); a tail pointer alone cannot fix this since it gives no backward link.

WATCH OUT FOR

Assuming a separate tail pointer makes dequeue O(1) too, forgetting that in a singly linked list the tail node has no back-pointer, so finding its predecessor still needs an O(n) scan from head.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes

More Linear structures questions