Stack Implementation Using Linked List in DSA Typescript - Deep Dive

Overview - Stack Implementation Using Linked List

What is it?

A stack is a collection where you add and remove items in a last-in, first-out order. Using a linked list means each item points to the next, making it easy to add or remove items without shifting others. This structure helps manage data where the most recent item is the first to be used. It works like a stack of plates where you only take from or add to the top.

Why it matters

Stacks solve problems where order matters, like undo actions or browser history. Without stacks, managing such tasks would be slow and complicated. Using a linked list for stacks avoids fixed size limits and costly data moves, making programs faster and more flexible. This helps software run smoothly and handle changing data easily.

Where it fits

Before learning this, you should understand basic linked lists and simple stack concepts. After this, you can explore stack applications like expression evaluation or recursion. This also prepares you for other dynamic data structures like queues or trees.

Mental Model

Core Idea

A stack using a linked list is like a chain where you add or remove links only at the front, keeping the newest item always on top.

Think of it like...

Imagine a stack of books where each book has a ribbon pointing to the one below it. You can only add or remove the top book, and the ribbon helps you find the next one easily.

Top -> [Node(value, next)] -> [Node(value, next)] -> ... -> null

Build-Up - 7 Steps

1

Foundation

Understanding Stack Basics

Concept: Learn what a stack is and how it works with simple push and pop operations.

A stack stores items in a last-in, first-out order. Push adds an item on top. Pop removes the top item. Think of a stack of plates: you add or remove only the top plate.

Result

You can add and remove items only from the top, following last-in, first-out.

Understanding the push and pop rules is key to using stacks correctly in any context.

2

Foundation

Basics of Linked List Structure

Concept: Learn how linked lists store data with nodes pointing to the next node.

A linked list is made of nodes. Each node holds a value and a pointer to the next node. The last node points to null, showing the end. This lets us add or remove nodes easily without moving others.

Result

You can create a chain of nodes where each knows the next, forming a flexible list.

Knowing how nodes link helps you build dynamic data structures that grow or shrink smoothly.

3

Intermediate

Combining Stack and Linked List

Concept: Use a linked list to build a stack where the head is the top of the stack.

In this stack, the linked list's head node is the top item. Push means creating a new node pointing to the current head, then updating head to this new node. Pop means removing the head node and moving head to the next node.

Result

Stack operations happen at the head, making push and pop fast and simple.

Using the head as the stack top leverages linked list flexibility for efficient stack operations.

4

Intermediate

Implementing Push Operation

🤔Before reading on: do you think push adds a node at the start or end of the linked list? Commit to your answer.

Concept: Push adds a new node at the start of the linked list to represent the top of the stack.

To push, create a new node with the value. Set its next pointer to the current head. Update head to this new node. This keeps the newest item on top.

Result

The stack grows by adding nodes at the front, keeping push O(1) time.

Knowing push adds at the front ensures fast insertion without traversing the list.

5

Intermediate

Implementing Pop Operation

🤔Before reading on: do you think pop removes the last node or the first node? Commit to your answer.

Concept: Pop removes the node at the start of the linked list, which is the top of the stack.

To pop, check if head is null (stack empty). If not, save the head's value, move head to head.next, and return the saved value. This removes the top item.

Result

The stack shrinks by removing the front node, keeping pop O(1) time.

Removing from the front avoids scanning the list, making pop efficient.

6

Advanced

Handling Edge Cases and Empty Stack

🤔Before reading on: do you think popping from an empty stack should return null, throw error, or something else? Commit to your answer.

Concept: Properly handle empty stack cases to avoid errors during pop or peek operations.

When popping or peeking, check if head is null. If yes, return null or throw an error to signal the stack is empty. This prevents crashes and informs users of invalid operations.

Result

Stack operations safely handle empty states without unexpected failures.

Handling empty stack cases prevents bugs and improves program reliability.

7

Expert

Memory and Performance Considerations

🤔Before reading on: do you think linked list stacks use more or less memory than array stacks? Commit to your answer.

Concept: Understand the memory overhead and performance tradeoffs of linked list stacks versus array stacks.

Linked list nodes store extra pointers, using more memory per item than arrays. But linked lists avoid resizing costs and wasted space. Push and pop are always O(1). Arrays may need resizing, causing slower operations occasionally.

Result

Linked list stacks offer consistent performance with flexible size but use more memory per element.

Knowing these tradeoffs helps choose the right stack type for different applications.

Under the Hood

Each stack node is an object with a value and a pointer to the next node. The stack keeps a reference to the head node, representing the top. Push creates a new node pointing to the current head and updates head. Pop removes the head node by moving head to the next node. This pointer manipulation happens in constant time without moving other nodes.

Why designed this way?

Linked lists were chosen to avoid fixed size limits of arrays and costly resizing. Using the head as the stack top simplifies operations to pointer changes only. This design balances speed and memory use, making stacks flexible and efficient for dynamic data.

Stack Top (head)
  ↓
+---------+      +---------+      +---------+
| Value A | ---> | Value B | ---> | Value C | ---> null
+---------+      +---------+      +---------+

Myth Busters - 3 Common Misconceptions

Quick: Does popping from a linked list stack remove the last node? Commit yes or no.

Common Belief: Popping removes the last node in the linked list because it's the last item added.

Reality: Popping removes the first node (head) because the stack top is at the head, not the tail.

Why it matters: Removing the wrong node would break the stack order and cause incorrect data retrieval.

Quick: Is push operation on a linked list stack O(n) or O(1)? Commit your answer.

Common Belief: Push takes O(n) time because you need to find the end of the list to add the new node.

Reality: Push is O(1) because the new node is added at the head, no traversal needed.

Why it matters: Thinking push is slow may discourage using linked list stacks where they are actually very efficient.

Quick: Can a linked list stack have a fixed size like an array stack? Commit yes or no.

Common Belief: Linked list stacks have a fixed size limit like arrays.

Reality: Linked list stacks grow dynamically with no fixed size limit until memory runs out.

Why it matters: Assuming fixed size limits can lead to unnecessary constraints or inefficient designs.

Expert Zone

1

Linked list stacks avoid resizing overhead but have extra memory cost per node due to pointers.

2

Garbage collection or manual memory management affects how popped nodes are cleaned up, impacting performance.

3

Stack nodes can be reused or pooled in high-performance systems to reduce allocation overhead.

When NOT to use

Avoid linked list stacks when memory is very limited or when cache locality is critical; array-based stacks are better then due to contiguous memory. Also, for very small fixed-size stacks, arrays are simpler and faster.

Production Patterns

Linked list stacks are used in interpreters for managing function calls, undo systems in editors, and parsing algorithms where dynamic size and fast push/pop are essential.

Connections

Recursion

Stacks model the call stack used in recursion, managing function calls and returns.

Understanding stack implementation helps grasp how recursive calls are tracked and unwound in programming languages.

Undo/Redo Systems

Stacks store user actions to allow undoing and redoing steps in applications.

Knowing stack behavior clarifies how software reverses or reapplies changes efficiently.

Linked List Data Structure

Stack implementation builds directly on linked list principles, using nodes and pointers.

Mastering linked lists is essential to implement and optimize stack operations.

Common Pitfalls

#1 Popping from an empty stack without checking causes errors.

Wrong approach:

function pop() {
const value = this.head.value;
this.head = this.head.next;
return value;
}

Correct approach:

function pop() {
if (!this.head) return null; // or throw error
const value = this.head.value;
this.head = this.head.next;
return value;
}

Root cause:

Not checking for empty stack leads to accessing properties of null, causing runtime errors.

#2 Adding new nodes at the tail instead of head makes push slow.

Wrong approach:

function push(value) {
let newNode = { value, next: null };
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}

Correct approach:

function push(value) {
let newNode = { value, next: this.head };
this.head = newNode;
}

Root cause:

Misunderstanding stack top location causes inefficient push by traversing the list.

#3 Not updating head pointer after pop leaves stale references.

Wrong approach:

function pop() {
if (!this.head) return null;
return this.head.value;
}

Correct approach:

function pop() {
if (!this.head) return null;
const value = this.head.value;
this.head = this.head.next;
return value;
}

Root cause:

Forgetting to move head pointer causes stack to never shrink, breaking expected behavior.

Key Takeaways

Stacks follow last-in, first-out order, making them perfect for tasks needing recent-first access.

Using a linked list for stacks allows dynamic size and fast push/pop by adding/removing nodes at the head.

Push and pop operations on linked list stacks run in constant time without traversing the list.

Properly handling empty stack cases prevents runtime errors and improves program stability.

Understanding memory and performance tradeoffs helps choose between linked list and array stacks in real applications.

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