Stack Implementation Using Linked List in DSA Java - Build from Scratch

Stack Implementation Using Linked List

📖 Scenario: Imagine you are building a simple undo feature for a text editor. Each action is stored in a stack. You will create a stack using a linked list to store these actions.

🎯 Goal: Build a stack data structure using a linked list in Java. You will create nodes, push actions onto the stack, pop actions from the stack, and display the stack content.

📋 What You'll Learn

Create a Node class with String data and Node next fields

Create a Stack class with a Node top field

Implement push(String action) method to add an action to the stack

Implement pop() method to remove and return the top action

Implement printStack() method to display all actions from top to bottom

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms.

💼 Career

Understanding stack implementation helps in software development roles involving data structure design and algorithm optimization.

1

Create Node class and Stack class with top

Create a Node class with String data and Node next fields. Then create a Stack class with a Node top field initialized to null.

DSA Java

// Define Node class
// Define Stack class with Node top initialized to null
// Your code here

Hint

Think of Node as a box holding the action and a link to the next box. The Stack keeps track of the top box.

2

Add push method to Stack

In the Stack class, add a method push(String action) that creates a new Node with action and places it on top of the stack.

DSA Java

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
        this.next = null;
    }
}

class Stack {
    Node top = null;

    // Add push method here
    // Your code here
}

Hint

Remember, pushing means putting the new node on top and linking it to the previous top.

3

Add pop method to Stack

In the Stack class, add a method pop() that removes the top Node from the stack and returns its data. If the stack is empty, return null.

DSA Java

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
        this.next = null;
    }
}

class Stack {
    Node top = null;

    void push(String action) {
        Node newNode = new Node(action);
        newNode.next = top;
        top = newNode;
    }

    // Add pop method here
    // Your code here
}

Hint

Pop means removing the top node and returning its data. If empty, return null.

4

Add printStack method and test stack operations

In the Stack class, add a method printStack() that prints all actions from top to bottom separated by -> . Then create a Main class with main method to push these actions in order: "Open File", "Edit Text", "Save File". Pop one action and print it. Finally, print the current stack.

DSA Java

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
        this.next = null;
    }
}

class Stack {
    Node top = null;

    void push(String action) {
        Node newNode = new Node(action);
        newNode.next = top;
        top = newNode;
    }

    String pop() {
        if (top == null) {
            return null;
        }
        String poppedData = top.data;
        top = top.next;
        return poppedData;
    }

    // Add printStack method here
    // Your code here
}

// Create Main class with main method
// Your code here

Hint

Print the popped action first, then print the stack from top to bottom separated by ' -> '.

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