Stack Implementation Using Linked List in DSA Typescript - Build from Scratch

Stack Implementation Using Linked List

📖 Scenario: Imagine you are building a simple undo feature for a text editor. Each action the user performs is saved in a stack. You will create this stack using a linked list to store actions.

🎯 Goal: Build a stack data structure using a linked list in TypeScript. You will create nodes, push actions onto the stack, pop actions from the stack, and finally display the stack contents.

📋 What You'll Learn

Create a Node class with value and next properties

Create a Stack class with top property initialized to null

Implement push method to add a new node on top

Implement pop method to remove the top node and return its value

Implement printStack method to display all values from top to bottom

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms.

💼 Career

Understanding stack implementation helps in software development roles involving data structures, algorithms, and system design.

1

Create Node class and Stack class with top property

Create a Node class with a constructor that takes a value of type string and a next property of type Node | null. Then create a Stack class with a top property initialized to null.

DSA Typescript

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

class Stack {
  top: Node | null = null;
  // Your code here
}

Hint

Define the Node class first with value and next. Then define the Stack class with top set to null.

2

Add push method to Stack class

Inside the Stack class, add a push method that takes a value of type string. Create a new Node with this value. Set the new node's next to the current top. Then update top to this new node.

DSA Typescript

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

class Stack {
  top: Node | null = null;

  push(value: string): void {
    // Your code here
  }
}

Hint

Create a new node with the given value. Point its next to the current top. Then update top to the new node.

3

Add pop method to Stack class

Inside the Stack class, add a pop method that returns a string | null. If top is null, return null. Otherwise, save the top node's value, update top to top.next, and return the saved value.

DSA Typescript

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

class Stack {
  top: Node | null = null;

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

  pop(): string | null {
    // Your code here
  }
}

Hint

Check if top is null. If yes, return null. Otherwise, save the value, move top to the next node, and return the saved value.

4

Add printStack method and test the stack

Inside the Stack class, add a printStack method that prints all values from top to bottom separated by ' -> ' and ending with 'null'. Then create a Stack instance, push 'Action1', 'Action2', and 'Action3', pop one action, and print the stack.

DSA Typescript

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

class Stack {
  top: Node | null = null;

  push(value: string): void {
    const newNode = new Node(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;
  }

  printStack(): void {
    // Your code here
  }
}

// Your code here

Hint

Traverse from top to null, building a string of values separated by ' -> '. Then print it. Test by pushing three actions, popping one, and printing.

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