Stack Using Linked List vs Array Stack Trade-offs in DSA Javascript - 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: Think of a stack like a stack of plates. Using an array is like a fixed-size tray where plates are stacked neatly but limited in space. Using a linked list is like stacking plates on a flexible pole that can grow or shrink as needed.

Array Stack:
[bottom] [1] -> [2] -> [3] [top]

Linked List Stack:
Top -> 3 -> 2 -> 1 -> null

Dry Run Walkthrough

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

Goal: Show how both stacks grow and shrink and highlight differences in resizing and memory

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

Array: [1]
Linked List: Top -> 1 -> null

Why: Start with empty stacks and add first item

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

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

Why: Add second item on top of the first

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

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

Why: Add third item on top, stacks grow

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

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

Why: Remove top item from both stacks

Result:

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

Annotated Code

DSA Javascript

class ArrayStack {
  constructor() {
    this.stack = [];
  }

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

  pop() {
    if (this.stack.length === 0) return null; // empty check
    return this.stack.pop(); // remove last item
  }

  print() {
    console.log(this.stack.join(', '));
  }
}

class LinkedListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
  }

  push(value) {
    const newNode = new LinkedListNode(value);
    newNode.next = this.top; // link new node to current top
    this.top = newNode; // update top to new node
  }

  pop() {
    if (!this.top) return null; // empty check
    const poppedValue = this.top.value;
    this.top = this.top.next; // move top down
    return poppedValue;
  }

  print() {
    let curr = this.top;
    const values = [];
    while (curr) {
      values.push(curr.value);
      curr = curr.next;
    }
    console.log(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
arrayStack.pop();
linkedListStack.pop();

// Print final stacks
console.log('Array Stack final:');
arrayStack.print();
console.log('Linked List Stack final:');
linkedListStack.print();

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

add new item on top of array stack

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

remove top item from array stack

newNode.next = this.top; // link new node to current top

link new node to current top node

this.top = newNode; // 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 final:

1, 2

Linked List Stack final:

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 stacks 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 null safely without error

DSA Javascript

if (this.stack.length === 0) return null; // empty check

Pop from empty linked list stack

Returns null safely without error

DSA Javascript

if (!this.top) return null; // empty check

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.

Common Mistakes

Mistake: Forgetting to update the top pointer after popping from linked list stack
Fix: Always set top to top.next after popping to remove the top node

Mistake: Assuming array stack never needs resizing
Fix: Remember arrays may need resizing which can cause slowdowns

Summary

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

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

The key insight is that array stacks are simple and fast but fixed size, while linked list stacks use extra memory but grow dynamically.

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 overall

D. Simpler syntax to implement

Solution

1. Step 1: Understand stack size behavior in arrays

   Arrays have fixed size or need resizing which costs time and memory.

2. Step 2: Understand linked list size behavior

   Linked lists grow dynamically by adding nodes without resizing.

3. Final Answer:

   Dynamic size without needing to resize -> Option A

4. Quick Check:

   Linked list stacks grow dynamically = B [OK]

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

Common Mistakes:

• Thinking arrays resize automatically without cost
• Confusing access speed advantage
• Assuming linked lists use less memory

2. Which of the following is the correct way to push an element onto a stack implemented using an array in JavaScript?

easy

A. stack.insert(element);

B. stack.add(element);

C. stack.append(element);

D. stack.push(element);

Solution

1. Step 1: Recall JavaScript array methods

   The method to add an element at the end of an array is push().

2. Step 2: Match method to stack push operation

   Stack push adds element on top, which is end of array, so push() is correct.

3. Final Answer:

   stack.push(element); -> Option D

4. Quick Check:

   Array push method = stack.push(element) [OK]

Hint: Use push() to add element at array end [OK]

Common Mistakes:

• Using non-existent methods like add() or append()
• Confusing push with pop
• Trying to use insert() which is not an array method

3. Consider this JavaScript code using a linked list stack implementation:

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

class Stack {
  constructor() {
    this.top = null;
  }
  push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
  }
  pop() {
    if (!this.top) return null;
    const val = this.top.value;
    this.top = this.top.next;
    return val;
  }
}

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

What is the output?

medium

A. 20
10
null

B. 10
20
null

C. null
10
20

D. 20
null
10

Solution

1. Step 1: Trace push operations

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

2. Step 2: Trace pop operations

   First pop returns 20, top moves to node with 10. Second pop returns 10, top becomes null. Third pop returns null as stack is empty.

3. Final Answer:

   20 10 null -> Option A

4. Quick Check:

   Stack LIFO pop order = 20, 10, null [OK]

Hint: Stack pops last pushed first (LIFO) [OK]

Common Mistakes:

• Assuming FIFO order instead of LIFO
• Forgetting to return null when empty
• Mixing push and pop order

4. The following code attempts to implement a stack using an array but has a bug:

class Stack {
  constructor() {
    this.items = [];
  }
  push(element) {
    this.items[this.items.length] = element;
  }
  pop() {
    return this.items.pop;
  }
}

What is the error and how to fix it?

medium

A. push method should use push() instead of indexing

B. pop method is missing parentheses; fix by using this.items.pop()

C. items array should be initialized as null

D. pop method should return this.items.pop without parentheses

Solution

1. Step 1: Identify pop method usage

   pop is a function, so calling this.items.pop without () returns the function itself, not the popped element.

2. Step 2: Fix pop method call

   Add parentheses to call the function: this.items.pop() returns the last element and removes it.

3. Final Answer:

   pop method is missing parentheses; fix by using this.items.pop() -> Option B

4. Quick Check:

   Call pop() with parentheses to execute [OK]

Hint: Remember to call pop() as a function with () [OK]

Common Mistakes:

• Forgetting parentheses on pop() call
• Changing push to incorrect method
• Initializing items as null instead of array

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

1. Array-based stack
2. Linked list-based stack

hard

A. Array stack, because it has faster push and pop operations always

B. Array stack, because arrays use less memory per element

C. Linked list stack, because it grows dynamically and avoids resizing overhead

D. Linked list stack, because it allows random access to elements

Solution

1. Step 1: Consider resizing overhead in array stacks

   Arrays need resizing when full, which is costly for millions of operations.

2. Step 2: Consider linked list memory and dynamic growth

   Linked lists grow node by node, avoiding resizing and memory waste from unused array slots.

3. Final Answer:

   Linked list stack, because it grows dynamically and avoids resizing overhead -> Option C

4. Quick Check:

   Dynamic growth avoids resizing overhead = A [OK]

Hint: For huge stacks, linked lists avoid costly resizing [OK]

Common Mistakes:

• Assuming arrays always have faster push/pop
• Ignoring resizing cost in arrays
• Thinking linked lists allow random access