How would you implement a queue using a singly linked list with head and tail pointers?

• A. Enqueue at head; dequeue from tail; update head and tail when empty; operations O(1).
• B. Enqueue at tail; dequeue from head; update head and tail when empty; operations O(1).
• C. Enqueue at head; dequeue from head; update only the head pointer; operations O(n).
• D. Enqueue at tail; dequeue from tail; uses a dummy node.

Answer: (B)

The main idea here is to support a queue with constant-time operations by keeping direct references to both ends of the list. With a singly linked list, that means maintaining a head pointer for the front of the queue and a tail pointer for the back.

To enqueue in O(1), add the new element at the tail: create a node for the new value, link the current tail to this node, and move the tail reference to the new node. If the queue was empty before this operation, both head and tail should point to the new node. This preserves the order: elements come out in the same order they went in.

To dequeue in O(1), remove the element at the head: take the node at head, move head to head.next, and if after the removal the queue becomes empty, set tail to NULL as well. The value you remove is always the oldest enqueued, which gives the FIFO behavior.

This combination—enqueue at the tail and dequeue from the head, with careful updates when the queue becomes empty—provides true queue semantics and constant-time operations. Enqueuing at the head and dequeuing from the head would produce LIFO behavior, not a queue, and dequeuing from the tail in a singly linked list would require traversing the list to find the predecessor, making it O(n). Using a dummy node doesn’t by itself fix the need to remove from the tail in constant time without extra pointers.