Stack Implementation Using Linked List in DSA C++ - Build from Scratch

Stack Implementation Using Linked List

📖 Scenario: Imagine you are building a simple system to manage browser history using a stack. Each page visited is added to the stack, and when the user clicks back, the last visited page is removed.

🎯 Goal: You will create a stack using a linked list in C++. You will add nodes, manage the top pointer, and print the stack content.

📋 What You'll Learn

Create a Node struct with an integer data and a pointer to the next Node

Create a Stack class with a private Node pointer called top

Implement a push function to add elements to the stack

Implement a pop function to remove elements from the stack

Implement a printStack function to display the stack from top to bottom

💡 Why This Matters

🌍 Real World

Stacks are used in many places like undo features, browser history, and expression evaluation.

💼 Career

Understanding stack implementation helps in interviews and building efficient software that manages data in last-in-first-out order.

1

Create Node struct and Stack class with top pointer

Create a struct Node with an int data and a Node* next. Then create a class Stack with a private Node* top pointer initialized to nullptr.

DSA C++

// Define Node struct and Stack class with top pointer
// Your code here

Hint

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

2

Add push function to Stack class

Inside the Stack class, add a public void push(int value) function. It should create a new Node, set its data to value, link its next to the current top, and update top to this new node.

DSA C++

#include 

struct Node {
    int data;
    Node* next;
};

class Stack {
private:
    Node* top = nullptr;
public:
    void push(int value) {
        // Your code here
    }
};

Hint

Push means adding a new box on top. Make sure the new box points to the old top, then update top.

3

Add pop function to Stack class

Inside the Stack class, add a public int pop() function. It should check if top is nullptr and return -1 if empty. Otherwise, save top->data, move top to top->next, delete the old top node, and return the saved data.

DSA C++

#include 

struct Node {
    int data;
    Node* next;
};

class Stack {
private:
    Node* top = nullptr;
public:
    void push(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        // Your code here
    }
};

Hint

Pop means removing the top box and returning its number. Remember to free memory of the removed node.

4

Add printStack function and test the stack

Add a public void printStack() function in the Stack class. It should print all data values from top to the last node separated by -> and end with nullptr. Then in main(), create a Stack object, push 10, 20, 30, pop once, and print the stack.

DSA C++

#include 

struct Node {
    int data;
    Node* next;
};

class Stack {
private:
    Node* top = nullptr;
public:
    void push(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (top == nullptr) {
            return -1;
        }
        int value = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return value;
    }

    void printStack() {
        // Your code here
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.pop();
    // Your code here
    return 0;
}

Hint

Print each node's data followed by '->' until you reach the end, then print 'nullptr'.

In main, after popping, print the stack to see the current elements.

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