GATE CS 2018 Q3 — Arrays, Stacks and Queues

To determine the time complexity of the enqueue and dequeue operations, let's analyze how they are performed on the given non-circular singly linked list:

1. Enqueue Operation (Insertion at the Head)

To insert a new node at the head of the singly linked list:

1. Create a new node.
2. Set the next pointer of the new node to point to the current head node:
   new_node->next = head;
3. Update the head pointer to point to the new node:
   head = new_node;

Since we have direct access to the head pointer, this operation does not require traversing the list. Thus, the time complexity of enqueue is $\Theta(1)$.

2. Dequeue Operation (Deletion from the Tail)

To delete the node at the tail of the singly linked list:

1. We need to update the tail pointer to point to the second-to-last node (the predecessor of the current tail).
2. Because this is a singly linked list, there are no backward pointers. To find the predecessor of the tail, we must start at the head and traverse the entire list until we find the node whose next pointer points to tail.
3. This traversal requires visiting $n-1$ nodes, which takes linear time.

Thus, the time complexity of dequeue is $\Theta(n)$.

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