☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement stack using Linkedlist

Easy TUF ID 391 A2Z

Java source ↗ Edit this article ↗

Problem

Design a stack of integers (push, pop, top, isEmpty, size) whose storage is a singly linked list rather than an array. The stack must grow without a fixed capacity and release memory as elements are popped. Last in, first out: the most recently pushed element is the one pop removes and top reports.

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

Example 1

push(1), push(2), push(3), top(), pop(), pop(), size(), isEmpty()
output: 3, 3, 2, 1, false          // 3 was pushed last, so it comes out first

Example 2

push(4), pop(), push(8), top(), pop(), isEmpty()
output: 4, 8, 8, true              // a stack that is emptied must be reusable

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 IntStack {
    void push(int x);
    int pop();
    int top();
    boolean isEmpty();
    int size();
}

Approach 1: The tail is the top

Intuition. When people first draw a stack as a list they often put the oldest element first and append new elements at the end, so the list reads bottom to top. That works, but a singly linked list only knows where its head is. To push, we must walk from the head to the last node to attach the new one. To pop, we must walk to the second-to-last node so we can cut the last one off. To read the top, we walk to the end again. Every operation visits every node.

Algorithm.

  1. push(x): create a node. If the list is empty it becomes the head; otherwise walk cur from head until cur.next == null and set cur.next to the new node. Increment count.
  2. pop(): if empty, throw. If the head is the only node, remember its value and set head = null. Otherwise walk cur until cur.next.next == null, remember cur.next.val, set cur.next = null. Decrement count.
  3. top(): walk to the last node and return its value.
  4. isEmpty() is head == null; size() is count.
static class TailLinkedStack implements IntStack {
    private Node head;                       // bottom of the stack
    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;   // walk to the tail
            cur.next = node;
        }
        count++;
    }

    public int pop() {
        if (head == null) throw new NoSuchElementException("stack underflow");
        count--;
        if (head.next == null) {             // single node: the tail is the head itself
            int x = head.val;
            head = null;
            return x;
        }
        Node cur = head;
        while (cur.next.next != null) cur = cur.next;   // stop at the second-last node
        int x = cur.next.val;
        cur.next = null;                     // unlink the old tail
        return x;
    }

    public int top() {
        if (head == null) throw new NoSuchElementException("stack is empty");
        Node cur = head;
        while (cur.next != null) cur = cur.next;
        return cur.val;
    }

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

    public int size() {
        return count;
    }
}

Complexity. Time O(n) for push, pop and top, where n is the current size, because each walks the entire list. Space O(n) for the nodes, plus one reference per node for next.

A tail pointer would make push O(1), but pop would still be O(n) in a singly linked list: once the tail is removed, the new tail is the node before it, and the only way to find that node is to walk from the head. Doubly linked nodes fix this at the cost of a second reference per node. The cleaner fix is to put the top at the other end.

Approach 2: The head is the top

Intuition. The one place a singly linked list can insert and delete in constant time is its head. So let the head be the top of the stack. Pushing links the new node in front of the current head; popping unlinks the head and moves to head.next; top reads head.val. No traversal is ever needed, and because popped nodes are no longer referenced, the garbage collector reclaims them, so the stack shrinks as well as grows.

Algorithm.

  1. push(x): create a node, set node.next = head, then head = node. Increment count.
  2. pop(): if head == null, throw. Remember head.val, set head = head.next, decrement count, return the value.
  3. top(): if empty throw, else return head.val.
  4. isEmpty() is head == null; size() is count.
static class HeadLinkedStack implements IntStack {
    private Node head;                       // top of the stack
    private int count = 0;

    public void push(int x) {
        Node node = new Node(x);
        node.next = head;                    // new node points at the old top
        head = node;
        count++;
    }

    public int pop() {
        if (head == null) throw new NoSuchElementException("stack underflow");
        int x = head.val;
        head = head.next;                    // the old top is now unreachable and gets collected
        count--;
        return x;
    }

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

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

    public int size() {
        return count;
    }
}

Dry run on example 1 (list written top → bottom):

operation list count returns
push(1) 1 1  
push(2) 2 → 1 2  
push(3) 3 → 2 → 1 3  
top() 3 → 2 → 1 3 3
pop() 2 → 1 2 3
pop() 1 1 2
size() 1 1 1
isEmpty() 1 1 false

Complexity. Time O(1) for every operation: each one touches only the head node and the count field. Space O(n) for n stored elements, with no wasted capacity and no copying when the stack grows.

Compared with an array-backed stack, the linked version never needs to resize and never over-allocates, but each element costs an object header and a next reference, and nodes are scattered in memory rather than contiguous. For a stack of primitives the array usually wins on speed; the linked list wins when sizes are unpredictable or when elements are large objects you would rather not copy.

Edge cases and pitfalls