☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement queue using Linkedlist

Easy TUF ID 388 A2Z

Java source ↗ Edit this article ↗

Problem

Design a queue of integers (push, pop, peek, isEmpty, size) whose storage is a singly linked list. The queue must grow without a fixed capacity. First in, first out: elements leave in the order they arrived.

Constraints: up to 10^5 operations, values fit in int. pop and peek on an empty queue are errors; the code throws NoSuchElementException.

Example 1

push(1), push(2), push(3), peek(), pop(), pop(), size(), isEmpty()
output: 1, 1, 2, 1, false          // 1 arrived first, so it leaves first

Example 2

push(1), pop(), push(2), push(3), peek(), pop(), pop(), isEmpty(), push(4), size()
output: 1, 2, 2, 3, true, 1        // the queue is emptied twice and must keep working

The list is built from this node type, and both implementations below satisfy the same interface so one test script drives them:

static class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
    }
}

interface IntQueue {
    void push(int x);
    int pop();
    int peek();
    boolean isEmpty();
    int size();
}

Approach 1: Head pointer only

Intuition. A queue removes from one end and inserts at the other. A singly linked list is cheap at its head, so let the head be the front: pop and peek work on head in constant time. Insertion then has to happen at the far end, and with only a head reference the only way to find the last node is to walk there. Every push traverses the whole list.

Algorithm.

  1. push(x): create a node. If head == null, it becomes the head. Otherwise walk cur from head while cur.next != null, then set cur.next to the new node. Increment count.
  2. pop(): if head == null, throw. Remember head.val, set head = head.next, decrement count, return the value.
  3. peek(): return head.val after the empty check.
  4. isEmpty() is head == null; size() is count.
static class HeadOnlyQueue implements IntQueue {
    private Node head;                       // front of the queue
    private int count = 0;

    public void push(int x) {
        Node node = new Node(x);
        if (head == null) {
            head = node;
        } else {
            Node cur = head;
            while (cur.next != null) cur = cur.next;   // find the rear every time
            cur.next = node;
        }
        count++;
    }

    public int pop() {
        if (head == null) throw new NoSuchElementException("queue underflow");
        int x = head.val;
        head = head.next;
        count--;
        return x;
    }

    public int peek() {
        if (head == null) throw new NoSuchElementException("queue is empty");
        return head.val;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int size() {
        return count;
    }
}

Complexity. Time O(n) for push, O(1) for pop, peek, isEmpty, size. Space O(n) for the nodes.

Pushing 10^5 elements one after another costs about 5 × 10^9 node visits in total, which is far too slow. The fix is obvious once stated: remember where the end is.

Approach 2: Head and tail pointers

Intuition. Keep a second reference, tail, to the last node. push then attaches the new node directly with tail.next = node and advances tail. pop still works at head. Both ends are reachable in constant time, which is exactly what a queue needs. The only subtlety is keeping the two references consistent when the queue goes from empty to one element and back.

Algorithm.

  1. push(x): create a node. If tail == null (the queue is empty), set head = node; otherwise set tail.next = node. In both cases set tail = node and increment count.
  2. pop(): if head == null, throw. Remember head.val and set head = head.next. If head is now null, the queue is empty, so set tail = null as well. Decrement count and return the value.
  3. peek(): return head.val after the empty check.
  4. isEmpty() is head == null; size() is count.
static class HeadTailQueue implements IntQueue {
    private Node head;                       // front: where pop happens
    private Node tail;                       // rear: where push happens
    private int count = 0;

    public void push(int x) {
        Node node = new Node(x);
        if (tail == null) {                  // empty queue: the new node is both front and rear
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        count++;
    }

    public int pop() {
        if (head == null) throw new NoSuchElementException("queue underflow");
        int x = head.val;
        head = head.next;
        if (head == null) tail = null;       // removed the last node: the rear must not dangle
        count--;
        return x;
    }

    public int peek() {
        if (head == null) throw new NoSuchElementException("queue is empty");
        return head.val;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int size() {
        return count;
    }
}

Dry run on example 2 (list written front → rear):

operation list head tail returns
push(1) 1 1 1  
pop() (empty) null null 1
push(2) 2 2 2  
push(3) 2 → 3 2 3  
peek() 2 → 3 2 3 2
pop() 3 3 3 2
pop() (empty) null null 3
isEmpty() (empty) null null true
push(4) 4 4 4  
size() 4 4 4 1

The second row is where the tail = null reset matters. Without it, tail would still point at the removed node 1; the next push(2) would attach 2 after that orphaned node and leave head as null, so the queue would look empty while holding an element.

Complexity. Time O(1) for every operation. Space O(n), with no spare capacity and no copying as the queue grows.

Compared with the circular-array queue, the linked version never needs to resize or compute indices modulo a capacity, but it spends an object header and a next reference per element, and its nodes are not contiguous in memory. For queues whose size swings widely, or whose elements are large objects, the linked list is the natural choice; for a bounded buffer of primitives the array is faster.

Edge cases and pitfalls