GATE CS 2018 Q.13 (CS Q.3): Stacks and Queues

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.

Singly linked list representation of a queue with head pointer at the first node and tail pointer at the last node.

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

$\theta(1), \theta(1)$

$\theta(1), \theta(n)$

$\theta(n), \theta(1)$

$\theta(n), \theta(n)$

Official answer and solution

Official answer: B
From: Official GATE 2018 answer key

Solution

Analyze head insertion and tail deletion in a non-circular singly linked list.

Enqueue is implemented by inserting a new node at head:

Allocate the new node, point its next pointer to head, and update head to the new node.
This requires a constant number of pointer assignments, running in $\Theta(1)$ time.

Dequeue is implemented by deleting the node at tail:

To delete the tail node, the next pointer of the $(n-1)$ -th node (the node immediately preceding tail) must be set to NULL, and tail must be updated to point to this node.
In a singly linked list with only forward pointers, the predecessor of tail cannot be reached directly from tail.
Finding the $(n-1)$ -th node requires traversing the list starting from head, which visits $n-1$ nodes and takes $\Theta(n)$ time.

Therefore, the time complexities are $\Theta(1)$ for enqueue and $\Theta(n)$ for dequeue.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 13 of 65, printed as CS Q.3
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source