Stack Implementation Using Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after these stack operations?

Consider a stack implemented using a linked list. The following operations are performed in order:

1. push(10)
2. push(20)
3. pop()
4. push(30)
5. peek()

What is the printed output of the peek() operation?

DSA Java

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

class Stack {
    Node top;
    void push(int x) {
        Node newNode = new Node(x);
        newNode.next = top;
        top = newNode;
    }
    int pop() {
        if (top == null) return -1;
        int val = top.data;
        top = top.next;
        return val;
    }
    int peek() {
        if (top == null) return -1;
        return top.data;
    }
}

public class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.push(10);
        s.push(20);
        s.pop();
        s.push(30);
        System.out.println(s.peek());
    }
}

A -1

B 30

C 10

D 20

💡 Hint

Remember that pop() removes the top element, and peek() shows the current top.

After pushing 10 and 20, the stack top is 20. Popping removes 20, so top becomes 10. Then pushing 30 makes top 30. So peek() returns 30.

🧠 Conceptual

intermediate

What is the time complexity of push and pop in a linked list stack?

For a stack implemented using a linked list, what is the time complexity of the push and pop operations?

A Both push and pop are O(1)

B Push is O(1), pop is O(n)

C Push is O(n), pop is O(1)

D Both push and pop are O(n)

💡 Hint

Think about how many nodes you need to traverse for push and pop.

Both push and pop operate only at the top node, so they take constant time O(1).

🔧 Debug

advanced

What error occurs when popping from an empty linked list stack?

Given the following pop method in a linked list stack, what error will occur if pop() is called on an empty stack?

int pop() {
    int val = top.data;
    top = top.next;
    return val;
}

A No error, returns 0

B IndexOutOfBoundsException

C StackOverflowError

D NullPointerException

💡 Hint

What happens if top is null and you try to access top.data?

If top is null, accessing top.data causes a NullPointerException.

❓ Predict Output

advanced

What is the stack content after these operations?

Consider a linked list stack initially empty. Perform these operations:

1. push(5)
2. push(15)
3. push(25)
4. pop()
5. push(35)

What is the printed stack content from top to bottom?

DSA Java

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

class Stack {
    Node top;
    void push(int x) {
        Node newNode = new Node(x);
        newNode.next = top;
        top = newNode;
    }
    int pop() {
        if (top == null) return -1;
        int val = top.data;
        top = top.next;
        return val;
    }
    void printStack() {
        Node curr = top;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.push(5);
        s.push(15);
        s.push(25);
        s.pop();
        s.push(35);
        s.printStack();
    }
}

A 35 -> 15 -> 5 -> null

B 25 -> 15 -> 5 -> null

C 15 -> 5 -> 35 -> null

D 5 -> 15 -> 35 -> null

💡 Hint

Remember that pop() removes the top element, and push() adds on top.

After pushing 5, 15, 25, the stack is 25 -> 15 -> 5. Popping removes 25, so stack is 15 -> 5. Pushing 35 adds it on top: 35 -> 15 -> 5.

🧠 Conceptual

expert

Why is linked list preferred over array for stack in some cases?

Which of the following is the best reason to use a linked list to implement a stack instead of an array?

A Linked list uses less memory than array always

B Linked list operations are faster than array operations in all cases

C Linked list allows dynamic size without resizing overhead

D Linked list allows random access to elements

💡 Hint

Think about resizing arrays and memory allocation.

Linked lists grow dynamically without needing to resize, unlike arrays which may need costly resizing.

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