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

Mental Model

A stack stores items in order, last in first out. You can build it using a linked list or an array, each with its own strengths and weaknesses.

Analogy: Imagine a stack of plates. Using an array is like a fixed shelf where plates are stacked in order, but the shelf size is fixed or needs resizing. Using a linked list is like stacking plates on a flexible pole where you can add or remove plates easily without worrying about shelf size.

Array Stack:
[0] 1
[1] 2
[2] 3 ↑top

Linked List Stack:
3 -> 2 -> 1 -> null ↑top

Dry Run Walkthrough

Input: Push 1, then 2, then 3 onto both stacks; then pop one item from each stack

Goal: Show how both stacks grow and shrink, and highlight differences in structure and operations

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

Array: [1] ↑top
Linked List: 1 -> null ↑top

Why: Start with one item in both stacks

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

Array: [1, 2] ↑top
Linked List: 2 -> 1 -> null ↑top

Why: Add second item on top of both stacks

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

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

Why: Add third item on top of both stacks

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

Array: [1, 2] ↑top
Linked List: 2 -> 1 -> null ↑top

Why: Remove top item from both stacks

Result:

Array Stack final: [1, 2] ↑top
Linked List Stack final: 2 -> 1 -> null ↑top

Annotated Code

DSA Typescript

class ArrayStack {
  private stack: number[] = [];

  push(value: number): void {
    this.stack.push(value); // add item at end
  }

  pop(): number | undefined {
    return this.stack.pop(); // remove last item
  }

  toString(): string {
    return this.stack.join(', ');
  }
}

class ListNode {
  value: number;
  next: ListNode | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class LinkedListStack {
  private top: ListNode | null = null;

  push(value: number): void {
    const node = new ListNode(value);
    node.next = this.top; // new node points to current top
    this.top = node; // update top to new node
  }

  pop(): number | undefined {
    if (!this.top) return undefined;
    const value = this.top.value;
    this.top = this.top.next; // move top down
    return value;
  }

  toString(): string {
    let curr = this.top;
    const values = [];
    while (curr) {
      values.push(curr.value);
      curr = curr.next;
    }
    return values.join(' -> ');
  }
}

// Driver code
const arrayStack = new ArrayStack();
const linkedListStack = new LinkedListStack();

// Push 1, 2, 3
[1, 2, 3].forEach(v => {
  arrayStack.push(v);
  linkedListStack.push(v);
});

// Pop one item
const arrayPop = arrayStack.pop();
const listPop = linkedListStack.pop();

console.log('Array Stack after pop:', arrayStack.toString());
console.log('Linked List Stack after pop:', linkedListStack.toString());

this.stack.push(value); // add item at end

Add new item to the end of the array stack

return this.stack.pop(); // remove last item

Remove and return the last item from the array stack

node.next = this.top; // new node points to current top

Link new node to current top in linked list stack

this.top = node; // update top to new node

Update top pointer to new node

this.top = this.top.next; // move top down

Remove top node by moving top pointer down

Output

Array Stack after pop: 1, 2

Linked List Stack after pop: 2 -> 1

Complexity Analysis

Time: O(1) for push and pop in both stacks because operations happen at one end only

Space: O(n) for both because they store all elements; linked list uses extra space for pointers

vs Alternative: Array stack may need resizing which can be costly; linked list stack uses more memory but grows flexibly without resizing

Edge Cases

Pop from empty stack

Returns undefined or no value safely without error

DSA Typescript

if (!this.top) return undefined;

Push many items exceeding initial array capacity

Array resizes internally, which may cause temporary slowdowns

DSA Typescript

this.stack.push(value); // array handles resizing internally

Single element stack pop

Stack becomes empty after pop

DSA Typescript

this.top = this.top.next; // top becomes null if last node removed

When to Use This Pattern

When you need a last-in-first-out structure and must choose between fixed size or flexible size, consider array stack for speed and linked list stack for dynamic size without resizing.

Common Mistakes

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

Mistake: Assuming array stack never needs resizing
Fix: Remember array may resize internally, which can affect performance

Summary

Stack stores items last-in-first-out using either array or linked list.

Use array stack for fast access when size is known or resizing is acceptable; use linked list stack for flexible size without resizing.

The key insight is array stacks have fixed capacity and resizing cost, linked list stacks use extra memory but grow smoothly.

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. Dynamic size without needing to resize

B. Faster access to elements by index

C. Uses less memory per element

D. Simpler syntax to implement

Solution

1. Step 1: Understand stack size behavior

   Arrays have fixed size or require resizing, linked lists grow dynamically.

2. Step 2: Compare memory and access

   Linked lists use extra memory for pointers and have slower indexed access.

3. Final Answer:

   Dynamic size without needing to resize -> Option A

4. Quick Check:

   Linked list stacks grow dynamically = A [OK]

Hint: Linked list stacks grow dynamically, arrays need resizing [OK]

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed advantages
• Assuming linked lists have simpler syntax

2. Which TypeScript syntax correctly declares an array-based stack of numbers?

easy

A. let stack = new Stack<number>();

B. const stack: number[] = [];

C. const stack: Array = number[];

D. var stack: number = [];

Solution

1. Step 1: Check array declaration syntax

   TypeScript arrays use type[] or Array<type> syntax.

2. Step 2: Validate each option

   const stack: number[] = []; uses correct syntax: number[] = []. Others have syntax errors or wrong types.

3. Final Answer:

   const stack: number[] = []; -> Option B

4. Quick Check:

   Correct array syntax = C [OK]

Hint: Array type syntax is type[] or Array<type> [OK]

Common Mistakes:

• Using wrong generic syntax
• Assigning array to wrong type variable
• Using var instead of const/let incorrectly

3. Consider this TypeScript code using an array stack:

const stack: number[] = [];
stack.push(10);
stack.push(20);
stack.pop();
stack.push(30);
console.log(stack);

What is the output?

medium

A. [10, 30]

B. [30]

C. [20, 30]

D. [10, 20, 30]

Solution

1. Step 1: Trace stack operations

   Push 10 -> [10], push 20 -> [10,20], pop removes 20 -> [10], push 30 -> [10,30]

2. Step 2: Check final stack content

   Stack contains 10 and 30 in order pushed and popped.

3. Final Answer:

   [10, 30] -> Option A

4. Quick Check:

   Push/pop trace = [10, 30] [OK]

Hint: Pop removes last pushed element, check stack after each step [OK]

Common Mistakes:

• Forgetting pop removes last element
• Assuming pop removes first element
• Confusing push order

4. This TypeScript code tries to implement a linked list stack but has an error:

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  top: Node | null = null;
  push(value: number) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
  }
  pop(): number | null {
    if (!this.top) return null;
    const val = this.top.value;
    this.top = this.top.next;
    return val;
  }
}

const stack = new Stack();
stack.push(5);
stack.push(10);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

What is the error in this code?

medium

A. Node class is missing a constructor

B. push() does not update the top pointer correctly

C. pop() returns null when stack is empty, which is correct behavior

D. Stack class does not initialize top to null

Solution

1. Step 1: Review pop() method behavior

   pop() returns null if stack is empty, which is expected to indicate empty stack.

2. Step 2: Check push() and initialization

   push() correctly updates top; Node has constructor; top initialized to null.

3. Final Answer:

   pop() returns null when stack is empty, which is correct behavior -> Option C

4. Quick Check:

   pop() returns null on empty stack = A [OK]

Hint: pop() returning null on empty stack is expected [OK]

Common Mistakes:

• Thinking pop() should throw error instead
• Believing push() does not update top
• Missing that top is initialized properly

5. You want to implement a stack that can handle millions of push/pop operations efficiently without resizing overhead. Which implementation is better and why?

hard

A. Array stack, because arrays have faster indexed access

B. Linked list stack, because it uses contiguous memory

C. Array stack, because it uses less memory per element

D. Linked list stack, because it avoids costly array resizing

Solution

1. Step 1: Consider resizing overhead in array stacks

   Arrays must resize and copy data when full, causing delays in many operations.

2. Step 2: Evaluate linked list advantages

   Linked lists grow dynamically without resizing, so push/pop remain efficient for large operations.

3. Final Answer:

   Linked list stack, because it avoids costly array resizing -> Option D

4. Quick Check:

   Dynamic growth avoids resizing = B [OK]

Hint: Avoid resizing overhead with linked list stacks for large operations [OK]

Common Mistakes:

• Assuming arrays never resize
• Confusing memory usage with speed
• Thinking linked lists use contiguous memory