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

Mental Model

A stack stores items in order, last in first out. It can be built using a linked list or an array, each with different strengths and weaknesses.

Analogy: Imagine a stack of plates. Using an array is like a fixed-size shelf where plates are stacked neatly but limited by shelf size. Using a linked list is like stacking plates on a flexible tower where you can add or remove plates without worrying about space but with a bit more overhead.

Array Stack:
[0] 5
[1] 3
[2] 7
[3] _
[4] _
Top -> [2]

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

Dry Run Walkthrough

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

Goal: Show how both stacks grow and shrink, highlighting differences in resizing and pointer updates

Step 1: Push 5 onto both stacks

Array Stack:
[0] 5
[1] _
[2] _
Top -> [0]

Linked List Stack:
5 -> null
↑ Top

Why: Add first element; both stacks start empty

Step 2: Push 3 onto both stacks

Array Stack:
[0] 5
[1] 3
[2] _
Top -> [1]

Linked List Stack:
3 -> 5 -> null
↑ Top

Why: Add second element; array uses next index, linked list adds new node at front

Step 3: Push 7 onto both stacks

Array Stack:
[0] 5
[1] 3
[2] 7
Top -> [2]

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

Why: Add third element; array fills next slot, linked list prepends node

Step 4: Pop one element from both stacks

Array Stack:
[0] 5
[1] 3
[2] _
Top -> [1]

Linked List Stack:
3 -> 5 -> null
↑ Top

Why: Remove top element; array moves top pointer back, linked list moves top pointer to next node

Result:

Array Stack:
[0] 5
[1] 3
[2] _
Top -> [1]

Linked List Stack:
3 -> 5 -> null
↑ Top

Annotated Code

DSA Java

class StackUsingArray {
    private int[] arr;
    private int top;

    public StackUsingArray(int size) {
        arr = new int[size];
        top = -1;
    }

    public void push(int val) {
        if (top == arr.length - 1) {
            resize(); // expand array when full
        }
        arr[++top] = val; // place val and move top
    }

    public int pop() {
        if (top == -1) throw new RuntimeException("Stack Underflow");
        return arr[top--]; // return top val and move top down
    }

    private void resize() {
        int[] newArr = new int[arr.length * 2];
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        arr = newArr; // replace with bigger array
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= top; i++) {
            sb.append(arr[i]).append(i == top ? "" : " -> ");
        }
        sb.append(" -> null");
        return sb.toString();
    }
}

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

class StackUsingLinkedList {
    private Node top;

    public void push(int val) {
        Node newNode = new Node(val);
        newNode.next = top; // new node points to current top
        top = newNode; // top moves to new node
    }

    public int pop() {
        if (top == null) throw new RuntimeException("Stack Underflow");
        int val = top.val;
        top = top.next; // top moves down one node
        return val;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node curr = top;
        while (curr != null) {
            sb.append(curr.val).append(curr.next == null ? "" : " -> ");
            curr = curr.next;
        }
        sb.append(" -> null");
        return sb.toString();
    }
}

public class StackTradeOffDemo {
    public static void main(String[] args) {
        StackUsingArray arrayStack = new StackUsingArray(3);
        StackUsingLinkedList linkedListStack = new StackUsingLinkedList();

        arrayStack.push(5);
        linkedListStack.push(5);

        arrayStack.push(3);
        linkedListStack.push(3);

        arrayStack.push(7);
        linkedListStack.push(7);

        System.out.println("Array Stack before pop: " + arrayStack);
        System.out.println("Linked List Stack before pop: " + linkedListStack);

        arrayStack.pop();
        linkedListStack.pop();

        System.out.println("Array Stack after pop: " + arrayStack);
        System.out.println("Linked List Stack after pop: " + linkedListStack);
    }
}

if (top == arr.length - 1) { resize(); }

expand array size when full to allow more pushes

arr[++top] = val;

increment top and place new value on array stack

return arr[top--];

return top value and decrement top pointer

newNode.next = top; top = newNode;

insert new node at front, update top pointer

int val = top.val; top = top.next;

save top value and move top pointer down one node

Output

Array Stack before pop: 5 -> 3 -> 7 -> null

Linked List Stack before pop: 7 -> 3 -> 5 -> null

Array Stack after pop: 5 -> 3 -> null

Linked List Stack after pop: 3 -> 5 -> null

Complexity Analysis

Time: O(1) average for push/pop because both use direct pointer/index updates; array resize is O(n) but rare

Space: O(n) for both; array uses contiguous memory, linked list uses extra memory per node for pointers

vs Alternative: Array stack is faster and cache-friendly but fixed size unless resized; linked list stack is flexible size but uses more memory and has pointer overhead

Edge Cases

Pushing beyond initial array size

Array stack resizes to double capacity to accommodate more elements

DSA Java

if (top == arr.length - 1) { resize(); }

Popping from empty stack

Throws RuntimeException 'Stack Underflow' to prevent invalid pop

DSA Java

if (top == -1) throw new RuntimeException("Stack Underflow");

Popping from empty linked list stack

Throws RuntimeException 'Stack Underflow' to prevent invalid pop

DSA Java

if (top == null) throw new RuntimeException("Stack Underflow");

When to Use This Pattern

When a problem requires last-in-first-out order and you must choose between fixed size or dynamic size, consider array stack for speed and linked list stack for flexibility.

Common Mistakes

Mistake: Not resizing array stack when full, causing overflow errors
Fix: Add a resize method and call it before pushing when array is full

Mistake: Forgetting to update top pointer after pop in linked list stack
Fix: Always move top to top.next after popping to remove the top node

Summary

It compares stack implementations using arrays and linked lists highlighting their trade-offs.

Use array stacks when you want fast access and know max size; use linked lists when size varies or is unknown.

The key insight is array stacks need resizing but are cache-friendly; linked lists are flexible but use extra memory for pointers.

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. Memory usage is always less than an array.

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

D. It uses less memory overhead per element.

Solution

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

   A linked list stack can grow dynamically as nodes are added, limited only by available memory.

2. Step 2: Compare with array stack size

   An array stack has a fixed size or requires resizing, which can be costly and limits immediate growth.

3. Final Answer:

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

4. Quick Check:

   Dynamic size = B [OK]

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

Common Mistakes:

• Thinking array stacks grow dynamically without resizing
• Assuming linked list uses less memory always
• Confusing access speed advantages

2. Which of the following is the correct way to declare an array-based stack of integers in Java?

easy

A. int stack = new int[10];

B. int[] stack = new int[10];

C. int[] stack = int[10];

D. int stack[] = int(10);

Solution

1. Step 1: Recall Java array declaration syntax

   In Java, arrays are declared with type[], variable = new type[size];

2. Step 2: Check each option

   int[] stack = new int[10]; matches correct syntax: int[] stack = new int[10]; others have syntax errors.

3. Final Answer:

   int[] stack = new int[10]; -> Option B

4. Quick Check:

   Correct Java array syntax = A [OK]

Hint: Java arrays use type[] var = new type[size]; [OK]

Common Mistakes:

• Missing 'new' keyword
• Using parentheses instead of brackets
• Declaring array without []

3. Consider the following Java code implementing a stack using a linked list. What will be printed after pushing 10, 20, then popping once?

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

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

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

medium

A. 20

B. null

C. 10

D. Compilation error

Solution

1. Step 1: Trace push operations

   Push 10: top points to node with 10. Push 20: top points to node with 20, next points to 10.

2. Step 2: Trace pop operation

   Pop removes top node (20), returns 20, top now points to node with 10.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Last pushed, first popped = 20 [OK]

Hint: Stack pop returns last pushed value [OK]

Common Mistakes:

• Confusing order of push and pop
• Assuming pop returns bottom element
• Ignoring null check in pop

4. The following code attempts to implement a stack using an array but has a bug. What is the error?

class ArrayStack {
  int[] stack = new int[5];
  int top = -1;
  void push(int x) {
    top++;
    stack[top] = x;
  }
}

medium

A. stack array should be declared static

B. top should start at 0, not -1

C. Array size should be dynamic

D. No check for stack overflow before push

Solution

1. Step 1: Analyze push method

   Push increments top and assigns value without checking if top exceeds array size.

2. Step 2: Identify missing overflow check

   Without checking top < stack.length, pushing beyond capacity causes ArrayIndexOutOfBoundsException.

3. Final Answer:

   No check for stack overflow before push -> Option D

4. Quick Check:

   Missing overflow check = A [OK]

Hint: Always check stack size before pushing [OK]

Common Mistakes:

• Assuming top starts at 0 is mandatory
• Thinking array must be dynamic always
• Confusing static keyword necessity

5. You need to implement a stack for a program where the maximum number of elements is unknown and memory efficiency is important. Which implementation is best and why?

hard

A. Linked list stack, because it grows dynamically and uses memory only as needed.

B. Linked list stack, because it uses less memory overhead per element than arrays.

C. Array stack, because it provides faster push and pop operations always.

D. Array stack, because arrays use less memory per element and resizing is automatic.

Solution

1. Step 1: Consider unknown max size and memory efficiency

   Unknown max size means dynamic growth is needed; linked list grows as needed without fixed size.

2. Step 2: Compare memory usage and operation speed

   Linked list uses extra memory per node for pointers but avoids wasted space from large arrays; resizing arrays can be costly.

3. Step 3: Choose best fit

   Linked list stack fits unknown size and memory efficiency better despite pointer overhead.

4. Final Answer:

   Linked list stack, because it grows dynamically and uses memory only as needed. -> Option A

5. Quick Check:

   Dynamic size + memory efficient = D [OK]

Hint: Unknown size? Use linked list stack for dynamic memory [OK]

Common Mistakes:

• Assuming arrays resize automatically without cost
• Ignoring pointer memory overhead in linked lists
• Confusing speed with memory efficiency