Implement Queue using Linked List

Implement a queue (first-in, first-out) backed by a singly linked list with a tail pointer, supporting:

push(x) — add x to the back of the queue.
pop() — remove and return the front element; return -1 if the queue is empty.

Both operations must be O(1).

Hints

· Stuck? Reveal one nudge at a time.

A singly linked list is O(1) at the head — how do you make the back O(1) too?

Keep a tail pointer so push appends without traversing.

Pop from the head; reset the tail to null when the queue empties.

Common doubts

Enqueue happens at the back. Without a tail pointer you'd traverse the whole list to find the last node (O(n)); the tail pointer makes it O(1).

The tail would still point at the removed node, so the next push links after a node that's no longer in the queue, corrupting it.

Interview follow-ups

· What an interviewer asks next.

Return head's value without advancing head — O(1).

A queue only needs O(1) at both ends, which a singly linked list with a tail pointer already provides; the extra prev pointers aren't needed.

Fun facts

This head/tail singly linked list is the standard implementation of a queue in most standard libraries' linked structures.
Lock-free concurrent queues (Michael–Scott) are built on exactly this head/tail node design with atomic pointer swaps.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: push(5), push(10), pop(), pop(), pop()
Output: 5, 10, -1
FIFO: 5 dequeues first, then 10, then -1.

Example 2

Input: push(7), pop()
Output: 7
Push 7, pop returns 7.

Constraints

- 1 <= number of operations <= 100 - 1 <= x <= 10^5 - pop() returns -1 if the queue is empty.

A queue needs O(1) at both ends: enqueue at the back, dequeue from the front. A singly linked list gives O(1) at the head for free; to make the back O(1) too, keep a tail pointer so you can append without traversing.

Prerequisites

Before you start

· Concepts used directly in the solution.

Singly linked list. Nodes with a value and a next pointer.

Tail pointer. A reference to the last node, so appends are O(1) instead of O(n).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The contract

“Which end enqueues and which dequeues?”

Enqueue (push) at the tail; dequeue (pop) at the head.

“What must I update when the queue becomes empty?”

When the last element is popped, reset the tail to null too.

The ideal opening — say it like this

I'll keep both a head and a tail pointer.

Push appends a node after the tail and advances the tail; pop removes the head and returns its value.

When the queue empties out, I reset the tail to null as well.

Understand the problem

Worked example — push 5, push 10, pop, pop, pop

push 5   -> head=tail-> [5]              (null)
push 10  -> head-> [5] -> [10] <-tail    (null)
pop      -> head-> [10] <-tail           returns 5
pop      -> head=tail=null               returns 10
pop      -> empty                        returns -1

Key observations

1Aha

A tail pointer makes enqueue O(1)

Without a tail pointer, appending to a singly linked list is O(n). Tracking the last node makes push O(1).

2Aha

Reset tail when the queue empties

Popping the last element leaves head null; the tail must be nulled too so a later push starts a fresh list rather than appending after a stale node.

Summary

Key takeaway

Keep head (front) and tail (back). push links a node after the tail and advances it; pop returns the head's value and advances the head, nulling the tail when the queue empties. Both operations are O(1).

push(x): node = Node(x); if tail: tail.next = node else head = node; tail = node
pop():   return -1 if head is null; val = head.val; head = head.next; if head is null: tail = null; return val