Stack Implementation Using Linked List in DSA Java

Mental Model

A stack is a collection where you add and remove items only from the top, like a stack of plates. Using a linked list means each item points to the one below it.

Analogy: Imagine a stack of books where you can only add or remove the top book. Each book has a note pointing to the book below it, so you know the order without moving all books.

Top -> [Node1] -> [Node2] -> [Node3] -> null
↑
stackTop

Dry Run Walkthrough

Input: Push values 10, then 20, then 30 onto an empty stack; then pop one value

Goal: Show how the stack grows with pushes and shrinks with a pop using linked list nodes

Step 1: Push 10: create new node with value 10, point it to current top (null), update top to new node

Top -> [10] -> null
↑
stackTop

Why: We add the first item, so top points to it and it points to null

Step 2: Push 20: create new node with value 20, point it to current top (10), update top to new node

Top -> [20] -> [10] -> null
↑
stackTop

Why: New item goes on top, so it points to previous top

Step 3: Push 30: create new node with value 30, point it to current top (20), update top to new node

Top -> [30] -> [20] -> [10] -> null
↑
stackTop

Why: Add new top node pointing to old top

Step 4: Pop: remove top node (30), update top to next node (20)

Top -> [20] -> [10] -> null
↑
stackTop

Why: Remove top item and move top pointer down

Result:

Top -> [20] -> [10] -> null
↑
stackTop
Popped value: 30

Annotated Code

DSA Java

public class StackUsingLinkedList {
    private static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node top;

    public StackUsingLinkedList() {
        this.top = null;
    }

    public void push(int value) {
        Node newNode = new Node(value); // create new node
        newNode.next = top; // new node points to current top
        top = newNode; // update top to new node
    }

    public int pop() {
        if (top == null) {
            throw new RuntimeException("Stack is empty");
        }
        int poppedValue = top.data; // get top value
        top = top.next; // move top down
        return poppedValue;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node current = top;
        while (current != null) {
            sb.append(current.data).append(" -> ");
            current = current.next;
        }
        sb.append("null");
        return sb.toString();
    }

    public static void main(String[] args) {
        StackUsingLinkedList stack = new StackUsingLinkedList();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.toString());
        int popped = stack.pop();
        System.out.println("Popped value: " + popped);
        System.out.println(stack.toString());
    }
}

Node newNode = new Node(value); // create new node

create a new node with the value to push

newNode.next = top; // new node points to current top

link new node to current top to keep stack order

top = newNode; // update top to new node

update top pointer to new node to make it the new top

if (top == null) { throw new RuntimeException("Stack is empty"); }

check if stack is empty before popping

int poppedValue = top.data; // get top value

store value of top node to return

top = top.next; // move top down

remove top node by moving top pointer to next node

Output

30 -> 20 -> 10 -> null

Popped value: 30

20 -> 10 -> null

Complexity Analysis

Time: O(1) because push and pop only change the top pointer and one node

Space: O(n) because each push adds one node to the linked list

vs Alternative: Compared to array-based stack, linked list stack avoids resizing but uses extra memory for pointers

Edge Cases

pop from empty stack

throws RuntimeException with message 'Stack is empty'

DSA Java

if (top == null) { throw new RuntimeException("Stack is empty"); }

push on empty stack

top points to new node with no next

DSA Java

newNode.next = top; // new node points to current top

When to Use This Pattern

When you need last-in-first-out order with dynamic size, use stack with linked list to efficiently add/remove from top.

Common Mistakes

Mistake: Not updating the top pointer after push or pop
Fix: Always assign top = newNode after push and top = top.next after pop

Mistake: Not handling empty stack before pop
Fix: Check if top is null and throw exception or handle empty case before popping

Summary

Implements a stack using a linked list where push and pop happen at the head.

Use when you want a stack that can grow without fixed size limits.

The top pointer always points to the newest item, making push/pop fast and simple.

Practice

1. What is the main advantage of implementing a stack using a linked list instead of an array?

easy

A. It uses less memory than an array

B. The stack can grow dynamically without a fixed size limit

C. It allows random access to elements

D. It is easier to sort the elements

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have a fixed size, so stacks implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic size advantage

   Linked lists can grow or shrink dynamically by adding or removing nodes, so the stack size is limited only by memory.

3. Final Answer:

   The stack can grow dynamically without a fixed size limit -> Option B

4. Quick Check:

   Dynamic size = Advantage of linked list stack [OK]

Hint: Linked list stacks grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked list uses less memory always
• Assuming stacks allow random access
• Confusing sorting with stack operations

2. Which of the following is the correct way to declare a node class for a linked list stack in Java?

easy

A. class Node { int data; int next; }

B. class Node { int data; Node prev; }

C. class Node { Node data; Node next; }

D. class Node { int data; Node next; }

Solution

1. Step 1: Identify node structure for linked list stack

   A node should store data and a reference to the next node.

2. Step 2: Check each option

   class Node { int data; Node next; } correctly uses 'int data' and 'Node next'. class Node { int data; Node prev; } uses 'prev' which is for doubly linked lists. class Node { int data; int next; } wrongly uses 'int next'. class Node { Node data; Node next; } wrongly uses 'Node data'.

3. Final Answer:

   class Node { int data; Node next; } -> Option D

4. Quick Check:

   Node stores data + next pointer [OK]

Hint: Node must have data and next pointer for stack [OK]

Common Mistakes:

• Using 'prev' pointer in singly linked list
• Declaring next as int instead of Node
• Using Node type for data field

3. What will be the output after the following operations on an empty linked list stack?

push(10); push(20); push(30); pop(); push(40);

Print the stack from top to bottom.

medium

A. 40 -> 30 -> 20 -> 10 -> null

B. 30 -> 20 -> 10 -> null

C. 40 -> 20 -> 10 -> null

D. 20 -> 10 -> null

Solution

1. Step 1: Trace push and pop operations

   push(10) -> stack: 10
   push(20) -> stack: 20 -> 10
   push(30) -> stack: 30 -> 20 -> 10
   pop() removes 30 -> stack: 20 -> 10
   push(40) -> stack: 40 -> 20 -> 10

2. Step 2: Write final stack order

   Top is 40, then 20, then 10, then null.

3. Final Answer:

   40 -> 20 -> 10 -> null -> Option C

4. Quick Check:

   Stack top after ops = 40 -> 20 -> 10 [OK]

Hint: Push adds top, pop removes top [OK]

Common Mistakes:

• Forgetting pop removes top element
• Appending instead of prepending on push
• Confusing order of elements after operations

4. Identify the error in the following pop method of a linked list stack:

public int pop() {
  if (top == null) {
    System.out.println("Stack Underflow");
  }
  int value = top.data;
  top = top.next;
  return value;
}

medium

A. It does not handle empty stack properly before accessing top.data

B. It should return void instead of int

C. It should update top.next instead of top

D. It should print "Stack Overflow" instead of "Stack Underflow"

Solution

1. Step 1: Check empty stack condition handling

   The method prints "Stack Underflow" but continues to access top.data without stopping or returning.

2. Step 2: Consequence of missing return or exception

   Accessing top.data when top is null causes NullPointerException. Proper handling requires returning or throwing after printing.

3. Final Answer:

   It does not handle empty stack properly before accessing top.data -> Option A

4. Quick Check:

   Null check must prevent access [OK]

Hint: Check for empty stack before accessing data [OK]

Common Mistakes:

• Not returning or throwing after underflow message
• Confusing overflow with underflow
• Updating wrong pointer in pop

5. You want to implement a method reverseStack() that reverses the elements of a linked list stack without using extra data structures. Which approach is best?

hard

A. Use recursion to pop all elements and push them back in reverse order

B. Traverse the linked list and swap data of nodes pairwise

C. Create a new linked list and copy elements in reverse order

D. Use a queue to dequeue and enqueue elements to reverse

Solution

1. Step 1: Understand constraints of no extra data structures

   Options C and D use extra structures (new list or queue), so they are invalid.

2. Step 2: Evaluate recursion and swapping

   Swapping data pairwise is complex and error-prone for linked list stack. Recursion can pop all elements and push back in reverse order naturally.

3. Final Answer:

   Use recursion to pop all elements and push them back in reverse order -> Option A

4. Quick Check:

   Recursion reverses stack without extra storage [OK]

Hint: Recursion can reverse stack without extra space [OK]

Common Mistakes:

• Using extra data structures despite constraints
• Trying to swap node data instead of nodes
• Confusing queue operations with stack reversal