Stack Implementation Using Linked List in DSA C++

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 bookmark pointing to the book below it, so you always know what comes next.

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

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 and shrinks using linked list nodes

Step 1: Push 10: create new node with value 10, point it to null, set top to this node

Top -> [10] -> null
          ↑

Why: We start the stack with one item, so top points to it

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
          ↑

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
          ↑

Why: Add new item on top, linking to previous top

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

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

Why: Remove the top item and move top pointer down

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class Stack {
private:
    Node* top;
public:
    Stack() : top(nullptr) {}

    void push(int val) {
        Node* newNode = new Node(val); // create new node
        newNode->next = top;           // link new node to current top
        top = newNode;                 // update top to new node
    }

    int pop() {
        if (top == nullptr) {
            cout << "Stack is empty" << endl;
            return -1; // indicate empty stack
        }
        int val = top->data;          // get top value
        Node* temp = top;             // save top node
        top = top->next;              // move top down
        delete temp;                  // free old top node
        return val;                  // return popped value
    }

    void display() {
        Node* curr = top;
        while (curr != nullptr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.display();
    int popped = s.pop();
    cout << "Popped value: " << popped << endl;
    s.display();
    return 0;
}

Node* newNode = new Node(val); // create new node newNode->next = top; // link new node to current top top = newNode; // update top to new node

Add new node on top by linking it to previous top and updating top pointer

if (top == nullptr) { cout << "Stack is empty" << endl; return -1; }

Check if stack is empty before popping to avoid errors

int val = top->data; // get top value Node* temp = top; // save top node top = top->next; // move top down delete temp; // free old top node return val;

Remove top node, update top pointer, free memory, and return popped value

while (curr != nullptr) { cout << curr->data << " -> "; curr = curr->next; }

Traverse from top to bottom to print stack contents

Output

30 -> 20 -> 10 -> null

Popped value: 30

20 -> 10 -> null

Complexity Analysis

Time: O(1) for push and pop because we only add or remove from the top without traversing

Space: O(n) because each pushed element creates a new node in memory

vs Alternative: Compared to array-based stack, linked list stack avoids fixed size limits and shifting elements but uses extra memory for pointers

Edge Cases

Pop from empty stack

Prints 'Stack is empty' and returns -1 without crashing

DSA C++

if (top == nullptr) {
            cout << "Stack is empty" << endl;
            return -1; // indicate empty stack
        }

When to Use This Pattern

When you need a stack that can grow dynamically without size limits, use a linked list stack to add and remove items efficiently from the top.

Common Mistakes

Mistake: Not updating the top pointer after push or pop, causing incorrect stack state
Fix: Always set top to the new node after push and to top->next after pop

Summary

Implements a stack using linked nodes where each new item is added or removed from the top.

Use when you want a stack that can grow without a fixed size and fast push/pop operations.

The key is to keep the top pointer updated to the newest node for quick access.

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 stack elements

Solution

1. Step 1: Understand stack size limitation in arrays

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

2. Step 2: Linked list dynamic size property

   Linked lists can grow or shrink dynamically by adding or removing nodes, so stack size is not fixed.

3. Final Answer:

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

4. Quick Check:

   Linked list stack size = dynamic growth [OK]

Hint: Linked list stacks grow dynamically, arrays have fixed size [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to create a new node in a linked list stack in C++?

easy

A. Node* newNode = new Node(value);

B. Node newNode = Node(value);

C. Node newNode = new Node(value);

D. Node* newNode = Node(value);

Solution

1. Step 1: Understand dynamic memory allocation in C++

   To create a node dynamically, use 'new' keyword and pointer type.

2. Step 2: Check syntax correctness

   Node* newNode = new Node(value); uses pointer and 'new' correctly: Node* newNode = new Node(value);

3. Final Answer:

   Node* newNode = new Node(value); -> Option A

4. Quick Check:

   Dynamic node creation = new + pointer [OK]

Hint: Use 'new' with pointer to create nodes dynamically [OK]

Common Mistakes:

• Omitting pointer (*) when using new
• Using stack allocation instead of dynamic
• Assigning new object to non-pointer variable

3. What will be the output after executing the following code snippet for a stack implemented using linked list?

Stack s;
s.push(10);
s.push(20);
s.push(30);
s.pop();
s.push(40);
s.display();

Assuming display prints elements from top to bottom.

medium

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

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

C. 20 -> 10 -> null

D. 40 -> 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: Determine display output

   Display prints from top to bottom: 40 -> 20 -> 10 -> null.

3. Final Answer:

   40 -> 20 -> 10 -> null -> Option D

4. Quick Check:

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

Hint: Track push/pop stepwise to find top element [OK]

Common Mistakes:

• Forgetting pop removes top element
• Assuming push adds at bottom
• Mixing order of elements in display

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

int pop() {
  if (top == NULL) {
    cout << "Stack Underflow";
    return -1;
  }
  int val = top->data;
  delete top;
  top = top->next;
  return val;
}

medium

A. Returning -1 on empty stack is incorrect

B. Missing check for stack overflow

C. Accessing top->next after deleting top causes undefined behavior

D. Not updating top pointer after pop

Solution

1. Step 1: Analyze order of operations in pop

   Code deletes top node before accessing top->next, which is unsafe.

2. Step 2: Identify correct order

   Must save top->next in a temp pointer before deleting top, then update top.

3. Final Answer:

   Accessing top->next after deleting top causes undefined behavior -> Option C

4. Quick Check:

   Delete before next access = error [OK]

Hint: Save next pointer before deleting current node [OK]

Common Mistakes:

• Deleting node before updating pointer
• Ignoring stack underflow check
• Returning wrong values on empty stack

5. You want to implement a function to reverse a stack implemented using a linked list without using extra data structures. Which approach is correct?

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 reorder elements and then push back to stack

Solution

1. Step 1: Understand constraints

   No extra data structures allowed, so cannot use queue or new list.

2. Step 2: Use recursion to reverse stack

   Recursion can pop all elements, then push them back in reverse order naturally.

3. Step 3: Why other options fail

   Swapping data pairwise does not reverse entire stack; copying needs extra list; queue is extra structure.

4. Final Answer:

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

5. Quick Check:

   Recursion reverses stack without extra structures [OK]

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

Common Mistakes:

• Using extra data structures despite constraints
• Trying to swap data instead of nodes
• Not understanding recursion stack behavior