Q&A

How to implement a queue using a linked list

By AlgoInsight Team2026-06-07data-structures

Overview

A queue serves elements in arrival order: you enqueue at the back and dequeue from the front, like a line of people. A linked-list implementation avoids the fixed capacity and costly resizing of an array, and - with both a front and rear pointer - achieves O(1) for both core operations.

graph LR
    F[front] --> N1[10] --> N2[20] --> N3[30] --> R[rear]
    R -.enqueue adds here.-> N4[40]
    F -.dequeue removes from here.-> N1
    style F fill:#1e1b4b,color:#fff
    style R fill:#1e1b4b,color:#fff

The Design

• Node: holds a value and a next pointer.
• front: points to the head node (oldest element) - remove here.
• rear: points to the tail node (newest element) - add here.
• Track size (optional but handy).

Keeping rear is the key trick: without it, enqueue would have to walk to the end (O(n)).

Java Implementation

public class LinkedQueue<T> {
    private static class Node<T> {
        T value;
        Node<T> next;
        Node(T value) { this.value = value; }
    }

    private Node<T> front;   // remove end
    private Node<T> rear;    // add end
    private int size;

    // enqueue: add to rear - O(1)
    public void enqueue(T value) {
        Node<T> node = new Node<>(value);
        if (rear == null) {            // empty queue
            front = rear = node;
        } else {
            rear.next = node;          // link old rear to new node
            rear = node;               // move rear pointer
        }
        size++;
    }

    // dequeue: remove from front - O(1)
    public T dequeue() {
        if (front == null) throw new java.util.NoSuchElementException("Queue is empty");
        T value = front.value;
        front = front.next;            // advance front
        if (front == null) rear = null; // queue became empty
        size--;
        return value;
    }

    public T peek() {
        if (front == null) throw new java.util.NoSuchElementException("Queue is empty");
        return front.value;
    }

    public boolean isEmpty() { return front == null; }
    public int size()        { return size; }
}

Usage

LinkedQueue<Integer> q = new LinkedQueue<>();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
System.out.println(q.dequeue());  // 10 (FIFO)
System.out.println(q.peek());     // 20

Python Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedQueue:
    def __init__(self):
        self.front = self.rear = None
        self.size = 0

    def enqueue(self, value):
        node = Node(value)
        if self.rear is None:
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node
        self.size += 1

    def dequeue(self):
        if self.front is None:
            raise IndexError("dequeue from empty queue")
        value = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        self.size -= 1
        return value

The Critical Edge Cases

1. Enqueue into an empty queue - both front and rear must point to the new node.
2. Dequeue the last element - after advancing front to null, you must also set rear = null, or rear dangles at a removed node and the next enqueue breaks.
3. Dequeue/peek on empty - throw or signal an error rather than dereferencing null.

These two pointer-bookkeeping cases are exactly what interviewers check.

Complexity

Linked List vs Array Implementation

• Linked list: no capacity limit, no resizing, O(1) ops; extra memory per node (pointer) and worse cache locality.
• Array (circular buffer): better cache performance and less per-element memory, but fixed capacity or amortized resizing.

In practice you'd often use a library deque (ArrayDeque in Java, collections.deque in Python), but implementing it shows you understand the structure.

Why This Matters in Interviews

This is a fundamental data-structure implementation question. Interviewers look for the two-pointer design (front + rear) giving O(1) both ways, and correct handling of the empty-queue and last-element edge cases (the rear = null reset is the classic bug). Comparing the linked-list and array trade-offs rounds out the answer.

Common Pitfalls

• Forgetting to set rear = null when the queue empties → dangling rear pointer.
• Not handling the first enqueue (both pointers must be set).
• Dequeuing/peeking an empty queue without an error check.
• Implementing without a rear pointer, making enqueue O(n).

References

• Queue (abstract data type): https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
• Java Queue/ArrayDeque: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Queue.html

More answers