Stack Using Linked List vs Array Stack Trade-offs in DSA C++ - Trade-offs & Analysis

Mental Model

A stack stores items in order, last in first out. Using an array or linked list changes how space and speed behave.

Analogy: Imagine stacking books on a table (array) versus stacking books on a flexible rope with knots (linked list). The table has fixed space, the rope can grow but needs knots to hold books.

Array Stack:
[0] 5
[1] 3
[2] 7
[3] null

Linked List Stack:
7 -> 3 -> 5 -> null
↑top

Dry Run Walkthrough

Input: Push 5, push 3, push 7, then pop one item from both array stack and linked list stack

Goal: Show how pushing and popping works differently and how space is used

Step 1: Push 5 onto array stack and linked list stack

Array: [0]5 -> [1]null -> [2]null -> [3]null
Linked List: 5 -> null ↑top

Why: Add first item to both stacks

Step 2: Push 3 onto array stack and linked list stack

Array: [0]5 -> [1]3 -> [2]null -> [3]null
Linked List: 3 -> 5 -> null ↑top

Why: Add second item on top of previous

Step 3: Push 7 onto array stack and linked list stack

Array: [0]5 -> [1]3 -> [2]7 -> [3]null
Linked List: 7 -> 3 -> 5 -> null ↑top

Why: Add third item on top

Step 4: Pop one item from array stack and linked list stack

Array: [0]5 -> [1]3 -> [2]null -> [3]null
Linked List: 3 -> 5 -> null ↑top

Why: Remove top item from both stacks

Result:

Array Stack final: 3 -> 5 -> null
Linked List Stack final: 3 -> 5 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Node for linked list stack
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// Linked list stack class
class LinkedListStack {
    Node* top;
public:
    LinkedListStack() : 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) return -1;          // empty stack check
        int val = top->data;          // get top value
        Node* temp = top;
        top = top->next;              // move top down
        delete temp;                  // free old top
        return val;
    }
    void print() {
        Node* curr = top;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

// Array stack class
class ArrayStack {
    int arr[4];
    int topIndex;
public:
    ArrayStack() : topIndex(-1) {}
    void push(int val) {
        if (topIndex == 3) return; // stack full
        arr[++topIndex] = val;     // add item on top
    }
    int pop() {
        if (topIndex == -1) return -1; // empty stack
        int val = arr[topIndex--];      // remove top item
        arr[topIndex + 1] = 0;          // optional: clear popped position
        return val;
    }
    void print() {
        for (int i = topIndex; i >= 0; i--) {
            cout << arr[i] << " -> ";
        }
        cout << "null" << endl;
    }
};

int main() {
    LinkedListStack llStack;
    ArrayStack arrStack;

    // Push 5, 3, 7
    llStack.push(5);
    arrStack.push(5);
    llStack.push(3);
    arrStack.push(3);
    llStack.push(7);
    arrStack.push(7);

    // Pop one item
    llStack.pop();
    arrStack.pop();

    // Print final stacks
    cout << "Linked List Stack: ";
    llStack.print();
    cout << "Array Stack: ";
    arrStack.print();

    return 0;
}

newNode->next = top; // link new node to current top

link new node to current top to keep stack order

top = newNode; // update top to new node

update top pointer to new node

top = top->next; // move top down

pop removes top by moving top pointer down

arr[++topIndex] = val; // add item on top

increment top index and add new value

return arr[topIndex--]; // remove top item

return top value and decrement top index

Output

Linked List Stack: 3 -> 5 -> null

Array Stack: 3 -> 5 -> null

Complexity Analysis

Time: O(1) for push and pop in both stacks because operations only change top pointer or index

Space: O(n) for linked list uses dynamic memory per element; O(n) fixed for array stack with fixed size

vs Alternative: Linked list stack can grow dynamically without fixed size limit but uses extra memory for pointers; array stack is faster in memory access but limited by fixed size

Edge Cases

Pushing to full array stack

Push is ignored because array is full

DSA C++

if (topIndex == 3) return; // stack full

Popping from empty stack

Returns -1 indicating empty stack

DSA C++

if (!top) return -1;          // empty stack check

Popping from empty array stack

Returns -1 indicating empty stack

DSA C++

if (topIndex == -1) return -1; // empty stack

When to Use This Pattern

When a problem needs last-in-first-out order and you must choose between fixed size or dynamic size, think about array stack vs linked list stack trade-offs.

Common Mistakes

Mistake: Not checking for stack overflow in array stack
Fix: Add condition to prevent pushing when array is full

Mistake: Not updating top pointer correctly in linked list pop
Fix: Move top pointer to next node before deleting old top

Summary

Stack using linked list or array stores data in last-in-first-out order with different memory and size trade-offs.

Use array stack for fixed size and faster access; use linked list stack for dynamic size without fixed limit.

The key insight is that array stack uses contiguous memory with fixed capacity, while linked list stack uses nodes linked by pointers allowing flexible size.

Practice

1. Which of the following is a key advantage of using a linked list to implement a stack compared to using an array?

easy

A. Accessing elements by index is faster.

B. The stack size can grow dynamically without a fixed limit.

C. Memory usage is always less than an array.

D. It uses less pointer memory.

Solution

1. Step 1: Understand stack size behavior in linked list

   A linked list stack can grow dynamically because nodes are created as needed without a fixed size.

2. Step 2: Compare with array stack size limits

   An array stack has a fixed size or requires resizing, which is costly. Linked list avoids this limitation.

3. Final Answer:

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

4. Quick Check:

   Dynamic size = Linked list advantage [OK]

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

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed advantages
• Assuming linked lists use less pointer memory

2. Which of the following is the correct way to declare a stack using an array in C++?

easy

A. int stack[10]; int top = -1;

B. int stack; int top = 0;

C. int stack[]; int top = -1;

D. int stack(10); int top = -1;

Solution

1. Step 1: Check array declaration syntax

   In C++, arrays are declared with size inside square brackets, e.g., int stack[10];

2. Step 2: Check top initialization

   Top is initialized to -1 to indicate empty stack.

3. Final Answer:

   int stack[10]; int top = -1; -> Option A

4. Quick Check:

   Correct array syntax and top init = C [OK]

Hint: Array size in [] brackets; top starts at -1 [OK]

Common Mistakes:

• Using parentheses instead of brackets for array
• Not initializing top correctly
• Declaring array without size

3. Consider the following code snippet implementing a stack push operation using a linked list:

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

Node* top = nullptr;

void push(int x) {
  Node* newNode = new Node();
  newNode->data = x;
  newNode->next = top;
  top = newNode;
}

push(10);
push(20);
push(30);

What will be the order of elements from top to bottom after these pushes?

medium

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

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

C. 30 -> 20 -> 10 -> null

D. 30 -> 10 -> 20 -> null

Solution

1. Step 1: Trace push operations on linked list stack

   Each push adds new node at the top, so last pushed is on top.

2. Step 2: Order after pushes

   push(10) -> top=10; push(20) -> top=20->10; push(30) -> top=30->20->10

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option C

4. Quick Check:

   Last in first out = 30 on top [OK]

Hint: Last pushed is always on top in linked list stack [OK]

Common Mistakes:

• Assuming order is 10->20->30
• Confusing push with append at end
• Ignoring pointer update order

4. The following code attempts to pop an element from an array-based stack but has a bug:

int stack[5];
int top = -1;

void pop() {
  if (top == 0) {
    cout << "Stack Underflow" << endl;
    return;
  }
  top--;
}

What is the bug in this pop function?

medium

A. It should print "Stack Overflow" instead of "Stack Underflow".

B. It should increment top instead of decrementing.

C. The stack array size is too small.

D. It should check if top == -1 for underflow, not top == 0.

Solution

1. Step 1: Understand stack underflow condition

   Underflow occurs when stack is empty, which is when top == -1.

2. Step 2: Check condition in code

   Code checks top == 0, which is wrong; top == 0 means one element is present.

3. Final Answer:

   It should check if top == -1 for underflow, not top == 0. -> Option D

4. Quick Check:

   Empty stack top = -1, check must match [OK]

Hint: Empty stack top is -1, check underflow with top == -1 [OK]

Common Mistakes:

• Checking top == 0 instead of -1
• Confusing overflow and underflow messages
• Incorrectly incrementing top on pop

5. You want to implement a stack that can handle millions of push and pop operations without worrying about maximum size. Which implementation is better and why?

1. Array-based stack with dynamic resizing
2. Linked list-based stack

hard

A. Linked list stack is better because it grows dynamically without resizing overhead.

B. Array stack is better because it uses less memory per element.

C. Array stack is better because dynamic resizing is always faster than linked list allocation.

D. Linked list stack is worse because it cannot grow beyond initial size.

Solution

1. Step 1: Consider dynamic resizing cost in array stack

   Array stack needs to resize and copy elements when full, which is costly for millions of operations.

2. Step 2: Consider linked list stack growth

   Linked list stack allocates nodes on demand, no resizing needed, so it handles large operations smoothly.

3. Final Answer:

   Linked list stack is better because it grows dynamically without resizing overhead. -> Option A

4. Quick Check:

   Dynamic growth without resizing = Linked list advantage [OK]

Hint: Linked list avoids resizing overhead for large stacks [OK]

Common Mistakes:

• Assuming array resizing is always faster
• Ignoring memory overhead of pointers
• Thinking linked list has fixed size