Stack Implementation Using Linked List in DSA Javascript - Execution Trace

Concept Flow - Stack Implementation Using Linked List

Create new node

↓

Push operation: newNode.next = top

↓

Update top = newNode

↓

Stack grows with new top

↓

Pop operation: if top != null

↓

Save top.data

↓

Update top = top.next

↓

Return saved data

↓

Stack shrinks from top

The stack adds new nodes at the top by linking them to the previous top, and removes nodes from the top by moving the top pointer to the next node.

Execution Sample

DSA Javascript

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
  }

  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
  }

  pop() {
    if (!this.top) return null;
    const popped = this.top.data;
    this.top = this.top.next;
    return popped;
  }
}

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

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize stack	None	top = null	top -> null
2	push(10)	Node(10)	newNode.next = null; top = newNode	top -> 10 -> null
3	push(20)	Node(20) -> Node(10)	newNode.next = top(10); top = newNode(20)	top -> 20 -> 10 -> null
4	push(30)	Node(30) -> Node(20) -> Node(10)	newNode.next = top(20); top = newNode(30)	top -> 30 -> 20 -> 10 -> null
5	pop()	Node(20) -> Node(10)	top = top.next (20)	top -> 20 -> 10 -> null; popped = 30
6	pop()	Node(10)	top = top.next (10)	top -> 10 -> null; popped = 20
7	pop()	None	top = top.next (null)	top -> null; popped = 10
8	pop()	None	top = null (unchanged)	top -> null; popped = null (stack empty)

💡 Stack is empty when top is null; pop returns null and stops.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
top	null	Node(10)	Node(20)	Node(30)	Node(20)	Node(10)	null	null
popped	N/A	N/A	N/A	N/A	30	20	10	null
stack size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

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

Because newNode.next must point to the current top node to keep the linked list connected. See step 3 where newNode.next = top(10) before top updates to newNode(20).

What happens if pop is called when the stack is empty?

Pop checks if top is null and returns null immediately without changing anything. See step 8 where pop returns null because top is already null.

Why does the stack grow and shrink only at the top?

Because push adds new nodes at the top and pop removes nodes from the top, keeping the last-in-first-out order. The pointer top always points to the newest node. See visual states in steps 2-7.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'top' after step 4?

A Node(10)

B Node(20)

C Node(30)

D null

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 4.

At which step does the stack become empty again?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the 'Nodes in List' and 'Visual State' columns to see when top becomes null.

If we push(40) after step 4, what will be the new top node's data?

A 40

B 20

C 30

D 10

💡 Hint

Push adds a new node at the top, so the new top data is the pushed value.

Concept Snapshot

Stack using linked list:
- push(data): create new node, link to current top, update top
- pop(): remove top node, update top to next
- top points to newest node
- Stack grows/shrinks at top only
- Empty stack when top is null

Full Transcript

This visualization shows how a stack is built using a linked list. Each push creates a new node that points to the current top, then updates top to this new node. Each pop removes the top node by moving top to the next node. The stack grows and shrinks only at the top, maintaining last-in-first-out order. When the stack is empty, top is null and pop returns null. The execution table tracks each step's nodes, pointer changes, and the visual linked list state. Variable tracker shows how top and popped values change over time. Key moments clarify why newNode.next is set before updating top, what happens when popping an empty stack, and why operations happen only at the top. The quiz tests understanding of top pointer values, when the stack empties, and push behavior.

Practice

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

easy

A. Dynamic size, no fixed limit on number of elements

B. Faster access to middle elements

C. Uses less memory for small stacks

D. Allows random access to elements

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have fixed size or require resizing, which can be costly.

2. Step 2: Linked list dynamic size advantage

   Linked lists grow and shrink dynamically without fixed size limits.

3. Final Answer:

   Dynamic size, no fixed limit on number of elements -> Option A

4. Quick Check:

   Linked list stacks grow dynamically [OK]

Hint: Linked list stacks grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked lists allow random access
• Confusing memory usage benefits
• Assuming arrays are always faster

2. Which of the following is the correct way to create a new node in a linked list stack in JavaScript?

easy

A. const node = Node(val, null);

B. const node = new Node(val, null);

C. const node = { value: val, next: null };

D. const node = { val: value, nextNode: null };

Solution

1. Step 1: Identify correct object property names

   Standard node uses 'value' and 'next' properties.

2. Step 2: Check JavaScript object literal syntax

   const node = { value: val, next: null }; correctly creates an object with 'value' and 'next' keys.

3. Final Answer:

   const node = { value: val, next: null }; -> Option C

4. Quick Check:

   Object with value and next keys [OK]

Hint: Node uses 'value' and 'next' keys in object [OK]

Common Mistakes:

• Using incorrect property names like 'val' or 'nextNode'
• Calling Node as a function without 'new'
• Missing 'const' or wrong syntax

3. What will be the output after pushing 10, then 20, then 30 onto an empty linked list stack and then popping once?

medium

A. Stack is empty

B. Stack top value is 10

C. Stack top value is 30

D. Stack top value is 20

Solution

1. Step 1: Push 10, 20, 30 in order

   Stack after pushes: top -> 30 -> 20 -> 10 -> null

2. Step 2: Pop once removes top (30)

   New top after pop is 20.

3. Final Answer:

   Stack top value is 20 -> Option D

4. Quick Check:

   Pop removes 30, next top is 20 [OK]

Hint: Last pushed is first popped, next top is previous push [OK]

Common Mistakes:

• Thinking pop removes bottom element
• Confusing order of pushes
• Assuming stack becomes empty after one pop

4. Given this pop method code for a linked list stack, what is the error?

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

medium

A. Should check if poppedNode.next exists before assigning

B. Should decrement stack size counter after pop

C. Should set poppedNode.next to null after popping

D. No error, code works correctly

Solution

1. Step 1: Analyze pop method logic

   Pop removes top node and returns its value correctly.

2. Step 2: Check for missing stack size update

   Stack size counter is not decremented, causing size mismatch.

3. Final Answer:

   Should decrement stack size counter after pop -> Option B

4. Quick Check:

   Pop must update size counter [OK]

Hint: Always update size counter on push/pop [OK]

Common Mistakes:

• Thinking next pointer must be cleared
• Assuming code returns wrong value
• Ignoring size counter updates

5. How would you modify a linked list stack to support a peek() method that returns the top element without removing it? Choose the correct implementation.

hard

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

B. peek() { const temp = this.pop(); this.push(temp); return temp; }

C. peek() { return this.top.next ? this.top.next.value : null; }

D. peek() { this.top = this.top.next; return this.top.value; }

Solution

1. Step 1: Understand peek method purpose

   Peek returns top value without changing stack.

2. Step 2: Evaluate each option

   peek() { return this.top ? this.top.value : null; } returns top value safely without modifying stack; others modify or access wrong nodes.

3. Final Answer:

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

4. Quick Check:

   Peek returns top value without removal [OK]

Hint: Peek reads top value, no pop or pointer changes [OK]

Common Mistakes:

• Using pop inside peek causing removal
• Accessing next node instead of top
• Changing top pointer in peek