Stacks from Scratch

IB Syllabus: B4.1.1 (HL) – Explain the properties and purpose of ADTs in programming. Implement a stack as an ADT using linked list nodes.

This page is HL only.

Key Concepts
Worked Examples
Quick Code Check
Trace Exercise
Code Completion
Spot the Bug
Output Prediction
Practice Exercises
1. Core
2. Extension
3. Challenge
Connections

Key Concepts

In Stacks you learned to use Java’s built-in Stack class – calling push, pop, and peek without worrying about how they work inside. On this page you will build a stack from scratch using linked list nodes, understanding every line of the implementation.

Using vs Building

Aspect	Using (B2.2.3)	Building (B4.1.1)
Code	`Stack<String> s = new Stack<>();`	Write your own `LinkedStack` class
Focus	What operations are available	How operations work internally
Knowledge	Interface only	Interface + implementation
Node class	Hidden inside Java library	You write it yourself

Stack Operations Recap

A stack follows the LIFO (Last In, First Out) principle:

Operation	Description	Time
`push(item)`	Add item to the top	O(1)
`pop()`	Remove and return item from the top	O(1)
`peek()`	View the top item without removing it	O(1)
`isEmpty()`	Check if the stack has no elements	O(1)
`size()`	Return the number of elements	O(1)

Why Use a Linked List?

A stack built with a linked list has no fixed capacity – it grows and shrinks dynamically. Each push creates a new node; each pop removes one. The top of the stack is the head of the linked list, so all operations are O(1) with no shifting.

An array-based stack is also possible but requires choosing a capacity upfront. If the array fills up, you must create a larger array and copy all elements – an expensive operation that a linked list avoids entirely.

Worked Examples

Example 1: LinkedStack Implementation

public class LinkedStack {
    private Node top;    // head of the linked list = top of stack
    private int count;

    public LinkedStack() {
        top = null;
        count = 0;
    }

    // Push: add to the top (front of linked list)
    public void push(String item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
        count++;
    }

    // Pop: remove and return from the top
    public String pop() {
        if (top == null) {
            System.out.println("Stack is empty");
            return null;
        }
        String data = top.data;
        top = top.next;
        count--;
        return data;
    }

    // Peek: view top without removing
    public String peek() {
        if (top == null) {
            System.out.println("Stack is empty");
            return null;
        }
        return top.data;
    }

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

    public int size() {
        return count;
    }

    public void printStack() {
        System.out.print("TOP -> ");
        Node current = top;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedStack stack = new LinkedStack();
        stack.push("Red");
        stack.push("Green");
        stack.push("Blue");

        stack.printStack();
        System.out.println("Peek: " + stack.peek());
        System.out.println("Size: " + stack.size());

        System.out.println("Pop: " + stack.pop());
        System.out.println("Pop: " + stack.pop());
        stack.printStack();
        System.out.println("Size: " + stack.size());
    }
}

Output:

TOP -> Blue -> Green -> Red -> null
Peek: Blue
Size: 3
Pop: Blue
Pop: Green
TOP -> Red -> null
Size: 1

Notice: push is identical to addToFront in a singly linked list. pop removes the head and returns its data. Both are O(1) – no traversal needed.

Example 2: Bracket Matching

A classic stack application: checking whether parentheses are balanced.

public class BracketChecker {
    public static boolean isBalanced(String expression) {
        LinkedStack stack = new LinkedStack();

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(String.valueOf(ch));
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;  // closing bracket with no opener
                }
                String opener = stack.pop();
                if (!matches(opener.charAt(0), ch)) {
                    return false;  // mismatched pair
                }
            }
        }
        return stack.isEmpty();  // true if all openers were matched
    }

    private static boolean matches(char open, char close) {
        return (open == '(' && close == ')')
            || (open == '[' && close == ']')
            || (open == '{' && close == '}');
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("((a + b) * c)"));
        System.out.println(isBalanced("{[()]}"));
        System.out.println(isBalanced("(a + b]"));
        System.out.println(isBalanced("((())"));
    }
}

Output:

true
true
false
false

Each opening bracket is pushed onto the stack. Each closing bracket pops the most recent opener and checks if they match. If the stack is empty at the end, every opener was matched.

Example 3: Reversing a String

Since a stack is LIFO, pushing characters and then popping them produces the reverse order.

public static String reverse(String input) {
    LinkedStack stack = new LinkedStack();
    for (int i = 0; i < input.length(); i++) {
        stack.push(String.valueOf(input.charAt(i)));
    }
    String result = "";
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

// reverse("HELLO") returns "OLLEH"

Quick Code Check

Q1. In a linked-list-based stack, which node represents the top of the stack?

Q2. The push operation on a linked stack is equivalent to which linked list operation?

Q3. What advantage does a linked-list stack have over an array-based stack?

Q4. What should pop() do if the stack is empty?

Q5. What is the time complexity of push, pop, and peek in a linked stack?

Trace Exercise

Trace the stack state after each operation.

LinkedStack s = new LinkedStack();
s.push("A");
s.push("B");
s.push("C");
s.pop();
s.push("D");
s.pop();

After operation	Stack (top to bottom)	size()
push("A")	A	1
push("B")		2
push("C")	C, B, A
pop() returns C		2
push("D")	D, B, A	3
pop() returns D

Code Completion

Complete the push method for a linked stack.

Fill in the blanks to add an item to the top of the stack:

public void push(String item) {
    Node newNode = new (item);
    newNode. = top;
     = newNode;
    count++;
}

Complete the pop method.

Fill in the blanks to remove and return the top item:

public String pop() {
    if (top == null) {
        return null;
    }
    String data = top.;
    top = top.;
    --;
    return data;
}

Spot the Bug

This push method causes an infinite loop when printing the stack:

1public void push(String item) { 2 Node newNode = new Node(item); 3 count++; 4 top = newNode; 5 newNode.next = top; 6}

Pick the correct fix:

This pop method returns the wrong item (the second item instead of the top):

1public String pop() { 2 if (top == null) { 3 return null; 4 } 5 top = top.next; 6 String data = top.data; 7 count--; 8 return data; 9}