Stack Implementation Using Linked List in DSA Typescript - Execution Trace

Concept Flow - Stack Implementation Using Linked List

Create new node with value

↓

Set new node.next to current top

↓

Update top pointer to new node

↓

Stack push complete

↓

Check if top is null?

Yes↓

Stack is empty

No↓

Access top node value

↓

Update top to top.next

↓

Stack pop complete

Push adds a new node at the top by linking it to the current top. Pop removes the top node by moving the top pointer to the next node.

Execution Sample

DSA Typescript

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 poppedValue = this.top.value;
    this.top = this.top.next;
    return poppedValue;
  }
}

This code defines a stack using a linked list where push adds a node at the top and pop removes the top node.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Push 10	10	top -> newNode(10)	10 -> null
2	Push 20	20 -> 10	newNode(20).next = top(10), top -> newNode(20)	20 -> 10 -> null
3	Push 30	30 -> 20 -> 10	newNode(30).next = top(20), top -> newNode(30)	30 -> 20 -> 10 -> null
4	Pop	20 -> 10	top moves from 30 to 20	20 -> 10 -> null
5	Pop	10	top moves from 20 to 10	10 -> null
6	Pop	empty	top moves from 10 to null	null
7	Pop on empty	empty	top is null, no change	null

💡 Execution stops after pop on empty stack returns null because stack is empty.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
top	null	Node(10)	Node(20)	Node(30)	Node(20)	Node(10)	null	null
stack size (count of nodes)	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why does push set newNode.next to the current top before updating top?

Because newNode.next must point to the previous top node to keep the linked list connected. See execution_table step 2 where newNode(20).next points to 10 before top updates.

What happens when pop is called on an empty stack?

The top pointer is null, so pop returns null immediately without changing anything. See execution_table step 7 where top remains null.

Why does pop update top to top.next instead of removing the node directly?

Because top.next points to the next node in the stack. Updating top to top.next effectively removes the current top node from the stack. See execution_table step 4 where top moves from 30 to 20.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the visual state of the stack?

A 30 -> 20 -> 10 -> null

B 20 -> 10 -> null

C 10 -> null

D null

💡 Hint

Check the Visual State column at step 3 in the execution_table.

At which step does the stack become empty?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at the Nodes in List column and find when it shows 'empty'.

If we push 40 after step 6, what will be the new top value?

A 10

B 30

C 40

D null

💡 Hint

After step 6, the stack is empty (top is null). Pushing 40 sets top to new node with value 40.

Concept Snapshot

Stack using linked list:
- Push: create new node, link to current top, update top
- Pop: return top value, update top to next node
- top points to the last pushed node
- Empty stack when top is null
- LIFO order: last in, first out

Full Transcript

This visualization shows how a stack is implemented using a linked list. Each push creates a new node and places it on top by linking it to the previous top node. The top pointer updates to this new node. Each pop removes the top node by moving the top pointer to the next node in the list. When the stack is empty, top is null. The execution table traces pushing 10, 20, 30, then popping three times until empty, and one extra pop on empty. The variable tracker shows how the top pointer and stack size change after each operation. Key moments clarify why new nodes link to the old top before updating, what happens when popping empty, and how pop updates top to remove nodes. The quiz tests understanding of stack state at various steps and effects of operations. This method ensures the stack follows last-in, first-out order using linked nodes.

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