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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Memory Usage Comparison

Which statement best describes the memory usage difference between a stack implemented using a linked list and one implemented using an array?

A Array stack uses extra memory for pointers, while linked list stack uses contiguous memory without extra pointers.

B Linked list stack uses extra memory for pointers, while array stack uses contiguous memory without extra pointers.

C Both linked list and array stacks use the same amount of memory per element.

D Linked list stack uses less memory overall because it stores only data without pointers.

💡 Hint

Think about how linked lists store elements compared to arrays.

A linked list stack stores each element in a node that contains the data and a pointer to the next node, which uses extra memory. An array stack stores elements in contiguous memory without pointers.

🧠 Conceptual

intermediate

Stack Size Flexibility

Which stack implementation allows dynamic resizing without a fixed maximum size?

A Linked list stack

B Array stack with fixed size array

C Array stack with static allocation

D Array stack with pre-allocated large size

💡 Hint

Consider which structure can grow without predefined limits.

Linked list stacks can grow dynamically by adding nodes, while fixed size arrays have a maximum capacity.

❓ Predict Output

advanced

Push Operation Time Complexity

What is the output of the following TypeScript code simulating push operations on both stack types?

DSA Typescript

class ArrayStack {
  private stack: number[] = [];
  push(item: number) {
    this.stack.push(item);
  }
  size() {
    return this.stack.length;
  }
}

class LinkedListNode {
  constructor(public value: number, public next: LinkedListNode | null = null) {}
}

class LinkedListStack {
  private head: LinkedListNode | null = null;
  private count = 0;
  push(item: number) {
    const node = new LinkedListNode(item, this.head);
    this.head = node;
    this.count++;
  }
  size() {
    return this.count;
  }
}

const arrayStack = new ArrayStack();
const linkedListStack = new LinkedListStack();

arrayStack.push(10);
arrayStack.push(20);
linkedListStack.push(10);
linkedListStack.push(20);

console.log(arrayStack.size());
console.log(linkedListStack.size());

A

2
1

B

1
2

C

2
2

D

0
0

💡 Hint

Count how many push operations were done on each stack.

Both stacks have two push operations, so their sizes are both 2.

❓ Predict Output

advanced

Pop Operation Behavior

What will be the output after popping one element from each stack below?

DSA Typescript

class ArrayStack {
  private stack: number[] = [];
  push(item: number) {
    this.stack.push(item);
  }
  pop() {
    return this.stack.pop();
  }
}

class LinkedListNode {
  constructor(public value: number, public next: LinkedListNode | null = null) {}
}

class LinkedListStack {
  private head: LinkedListNode | null = null;
  push(item: number) {
    const node = new LinkedListNode(item, this.head);
    this.head = node;
  }
  pop() {
    if (!this.head) return null;
    const val = this.head.value;
    this.head = this.head.next;
    return val;
  }
}

const arrayStack = new ArrayStack();
const linkedListStack = new LinkedListStack();

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

console.log(arrayStack.pop());
console.log(linkedListStack.pop());

A

15
15

B

5
15

C

15
5

D

5
5

💡 Hint

Stacks remove the last pushed item first.

Both stacks remove the last pushed element, which is 15.

🧠 Conceptual

expert

Performance Trade-offs in Large Scale

In a system where millions of push and pop operations occur frequently, which stack implementation trade-off is most significant?

A Array stack always uses less memory and has faster push/pop than linked list stack regardless of size.

B Linked list stack resizing is costly, array stack uses more memory per element due to pointers.

C Linked list stack uses contiguous memory which improves cache performance over array stack.

D Array stack may need resizing which can cause costly copying, linked list stack has consistent push/pop time but uses more memory per element.

💡 Hint

Think about resizing costs and memory overhead.

Array stacks may need to resize and copy elements, which is costly, while linked list stacks avoid resizing 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. 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