Stack Implementation Using Linked List in DSA Typescript

Mental Model

A stack is a collection where you add and remove items only from the top, like a stack of plates. Using a linked list means each item points to the one below it.

Analogy: Imagine stacking plates one on top of another. You always put a new plate on top and take the top plate off first. Each plate has a small tag pointing to the plate below it.

Top -> [Node] -> [Node] -> [Node] -> null
       ↑
     stackTop

Dry Run Walkthrough

Input: Push values 10, 20, then pop one value from the stack

Goal: Show how the stack changes with push and pop operations using a linked list

Step 1: Push 10 onto the stack

Top -> [10] -> null
       ↑

Why: We add the first node and it becomes the top

Step 2: Push 20 onto the stack

Top -> [20] -> [10] -> null
       ↑

Why: New node points to previous top, then becomes new top

Step 3: Pop the top value from the stack

Top -> [10] -> null
       ↑

Why: Remove top node by moving top pointer to next node

Result:

Top -> [10] -> null
       ↑
Popped value: 20

Annotated Code

DSA Typescript

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

class Stack {
  private top: Node | null;

  constructor() {
    this.top = null;
  }

  push(value: number): void {
    const newNode = new Node(value);
    newNode.next = this.top; // new node points to current top
    this.top = newNode; // new node becomes the top
  }

  pop(): number | null {
    if (this.top === null) {
      return null; // stack empty
    }
    const poppedValue = this.top.value;
    this.top = this.top.next; // move top to next node
    return poppedValue;
  }

  printStack(): void {
    let current = this.top;
    let result = '';
    while (current !== null) {
      result += current.value + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.printStack();
const popped = stack.pop();
console.log('Popped value:', popped);
stack.printStack();

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

link new node to current top to keep stack order

this.top = newNode; // new node becomes the top

update top pointer to new node

if (this.top === null) { return null; } // stack empty check

handle empty stack before pop

this.top = this.top.next; // move top to next node

remove top node by moving pointer down

Output

20 -> 10 -> null

Popped value: 20

10 -> null

Complexity Analysis

Time: O(1) for push and pop because we only change the top pointer without traversing the list

Space: O(n) because each pushed value creates a new node stored in memory

vs Alternative: Compared to array-based stack, linked list avoids resizing but uses extra memory for pointers

Edge Cases

Pop from an empty stack

Returns null safely without error

DSA Typescript

if (this.top === null) { return null; } // stack empty check

Push to an empty stack

Creates first node and sets it as top

DSA Typescript

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

When to Use This Pattern

When you need last-in-first-out order with dynamic size and fast push/pop, use stack with linked list to avoid resizing overhead.

Common Mistakes

Mistake: Not updating the top pointer after push or pop
Fix: Always assign the new node to top after push and move top to next after pop

Mistake: Forgetting to handle empty stack in pop
Fix: Check if top is null before popping to avoid errors

Summary

Implements a stack using a linked list where push and pop happen at the head.

Use when you want a stack with dynamic size and constant time push/pop.

The key is to always add or remove nodes from the top pointer to keep stack order.

Practice

1. What is the main advantage of implementing a stack using a linked list instead of an array?

easy

A. It allows random access to elements

B. It uses less memory than an array

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

D. It is faster to access elements by index

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have a fixed size, so stacks implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic size

   Linked lists can grow or shrink dynamically by adding or removing nodes, so stack size is not fixed.

3. Final Answer:

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

4. Quick Check:

   Linked list stacks grow dynamically = A [OK]

Hint: Linked list stacks grow dynamically, arrays do not [OK]

Common Mistakes:

• Thinking linked lists use less memory always
• Confusing stack with queue behavior
• Assuming random access is possible in linked lists

2. Which of the following is the correct TypeScript syntax to define a node class for a linked list stack?

easy

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

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

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

D. class Node { value: number; next: any; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check next pointer type

   In a linked list, next can be another node or null if it's the last node.

2. Step 2: Verify constructor initialization

   The constructor sets value and initializes next to null.

3. Final Answer:

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

4. Quick Check:

   next can be Node or null = B [OK]

Hint: next must allow null for last node [OK]

Common Mistakes:

• Not allowing next to be null
• Initializing next as undefined
• Using incorrect type for next

3. Given the following TypeScript code for a stack push operation, what will be the top node's value after pushing 10, then 20?

medium

A. undefined

B. 10

C. null

D. 20

Solution

1. Step 1: Understand push operation

   Push adds a new node at the top, so the last pushed value becomes the top.

2. Step 2: Trace pushing 10 then 20

   First push 10: top.value = 10; then push 20: top.value = 20 (new node).

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Last pushed value is top = 20 [OK]

Hint: Top always holds last pushed value [OK]

Common Mistakes:

• Assuming bottom value is top
• Confusing push with pop
• Not updating top pointer

4. Identify the error in this pop method of a linked list stack implementation:

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

medium

A. Returns the new top value instead of popped value

B. Does not check if stack is empty

C. Does not update top pointer

D. Throws error when stack is empty

Solution

1. Step 1: Analyze return value

   The method returns this.top.value after updating top, which is the new top, not the popped value.

2. Step 2: Correct return value

   It should return the saved value before updating top to return the popped element.

3. Final Answer:

   Returns the new top value instead of popped value -> Option A

4. Quick Check:

   Pop must return popped value, not new top [OK]

Hint: Return saved value before updating top [OK]

Common Mistakes:

• Returning top after update instead of popped value
• Not handling empty stack
• Forgetting to update top pointer

5. You want to implement a method peek() in your linked list stack that returns the top value without removing it. Which is the correct implementation?

hard

A. peek(): number | null { return this.top ? this.top.value : null; }

B. peek(): number | null { const val = this.top.value; this.top = this.top.next; return val; }

C. peek(): number | null { if (!this.top) return null; this.top = this.top.next; return this.top.value; }

D. peek(): number | null { return this.top.next ? this.top.next.value : null; }

Solution

1. Step 1: Understand peek operation

   Peek returns the top value without changing the stack.

2. Step 2: Check each option

   peek(): number | null { return this.top ? this.top.value : null; } returns top value if exists, else null, without modifying stack. Others modify top or return wrong node.

3. Final Answer:

   peek(): number | null { return this.top ? this.top.value : null; } -> Option A

4. Quick Check:

   Peek returns top value without removal = C [OK]

Hint: Peek returns top value without changing stack [OK]

Common Mistakes:

• Modifying top pointer in peek
• Returning next node's value
• Not handling empty stack