Stack Implementation Using Linked List in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack and how does it work?

A stack is a collection where elements are added and removed from only one end called the top. It works on Last In, First Out (LIFO) principle, meaning the last item added is the first to be removed.

beginner

What is the role of a linked list in stack implementation?

A linked list stores stack elements as nodes connected by links. Each node holds data and a reference to the next node. This allows dynamic memory use and easy addition/removal at the top.

intermediate

Explain the push operation in a stack implemented with a linked list.

Push adds a new node at the top of the stack. The new node's next pointer points to the current top node, then the top reference updates to the new node.

intermediate

How does the pop operation work in a linked list stack?

Pop removes the top node from the stack. The top reference moves to the next node of the current top, effectively removing the first node and returning its data.

beginner

What happens when you try to pop from an empty stack?

Trying to pop from an empty stack results in an underflow condition. It means there are no elements to remove, so the operation should handle this safely, often by returning null or throwing an exception.

What principle does a stack follow?

A Random Access

B First In, First Out (FIFO)

C Priority Based

D Last In, First Out (LIFO)

Stacks follow the Last In, First Out (LIFO) principle where the last element added is the first to be removed.

In a linked list stack, where is the new element added during push?

A At the bottom (tail) of the list

B At the top (head) of the list

C In the middle of the list

D At a random position

Push operation adds the new element at the top (head) of the linked list representing the stack.

What does the pop operation do in a linked list stack?

A Removes the top node and returns its data

B Adds a new node at the top

C Removes the bottom node

D Returns the size of the stack

Pop removes the top node from the stack and returns its data.

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

A O(1)

B O(n)

C O(log n)

D O(n^2)

Both push and pop operations take constant time O(1) because they only modify the top node.

What should happen if pop is called on an empty stack?

A Return the last element

B Add a new element

C Return null or throw an exception

D Do nothing silently

Pop on an empty stack should safely handle underflow by returning null or throwing an exception.

Describe how a stack is implemented using a linked list and explain the push and pop operations.

Think about how nodes are added and removed at the head of the list.

What are the advantages of using a linked list to implement a stack compared to using an array?

Consider memory and resizing differences.

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