Stack Using Linked List vs Array Stack Trade-offs in DSA Typescript - Build Both Approaches

Stack Using Linked List vs Array Stack Trade-offs

📖 Scenario: You are building a simple stack to manage tasks in a to-do list app. You want to understand how using a linked list or an array affects your stack's behavior and performance.

🎯 Goal: Create two stacks: one using a linked list and one using an array. Push and pop items to see how each works and compare their outputs.

📋 What You'll Learn

Create a linked list node class called ListNode with value and next properties

Create a LinkedListStack class with push, pop, and printStack methods

Create an ArrayStack class with push, pop, and printStack methods

Push the same items to both stacks and pop one item from each

Print the contents of both stacks after operations

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and managing function calls in programming languages.

💼 Career

Understanding stack implementations helps in optimizing memory and performance in software development and system design.

1

Create Linked List Node and LinkedListStack Class

Create a class called ListNode with a constructor that takes a value of type string and a next property initialized to null. Then create a class called LinkedListStack with a top property initialized to null.

DSA Typescript

// Define ListNode class
// Define LinkedListStack class with top property
// Your code here

Hint

Think of ListNode as a box holding a value and a pointer to the next box. The LinkedListStack keeps track of the top box.

2

Add push and pop Methods to LinkedListStack

Add a push method to LinkedListStack that takes a value string, creates a new ListNode, and sets it as the new top. Add a pop method that removes and returns the top node's value or returns null if empty.

DSA Typescript

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

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

    // Add push method here
    // Add pop method here
    // Your code here
}

Hint

Push adds a new node on top. Pop removes the top node and returns its value.

3

Create ArrayStack Class with push and pop Methods

Create a class called ArrayStack with a private array property called items initialized as an empty array. Add a push method that adds a string to items and a pop method that removes and returns the last string or returns null if empty.

DSA Typescript

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

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

    push(value: string): void {
        const newNode = new ListNode(value);
        newNode.next = this.top;
        this.top = newNode;
    }

    pop(): string | null {
        if (this.top === null) return null;
        const poppedValue = this.top.value;
        this.top = this.top.next;
        return poppedValue;
    }
}

// Define ArrayStack class with items array
// Add push and pop methods
// Your code here

Hint

ArrayStack uses a simple array to hold items. Push adds to the end, pop removes from the end.

4

Push and Pop Items, Then Print Both Stacks

Create instances of LinkedListStack and ArrayStack. Push the strings "task1", "task2", and "task3" to both stacks. Pop one item from each stack. Then print the remaining items in both stacks using a printStack method you add to each class that prints items from top to bottom separated by ' -> ' and ending with ' -> null'.

DSA Typescript

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

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

    push(value: string): void {
        const newNode = new ListNode(value);
        newNode.next = this.top;
        this.top = newNode;
    }

    pop(): string | null {
        if (this.top === null) return null;
        const poppedValue = this.top.value;
        this.top = this.top.next;
        return poppedValue;
    }

    // Add printStack method here
}

class ArrayStack {
    private items: string[];
    constructor() {
        this.items = [];
    }

    push(value: string): void {
        this.items.push(value);
    }

    pop(): string | null {
        if (this.items.length === 0) return null;
        return this.items.pop() || null;
    }

    // Add printStack method here
}

// Create instances, push "task1", "task2", "task3", pop one item, then print stacks
// Your code here

Hint

Print from top to bottom for linked list by following next. For array, print from last to first element.

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