Stack Implementation Using Linked List in DSA Javascript

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 next, so we can easily add or remove the top item.

Analogy: Imagine a stack of plates where you always put a new plate on top and take the top plate off. Each plate has a small tag pointing to the plate below it, so you know the order without moving all plates.

Top -> [Node1] -> [Node2] -> [Node3] -> null
       ↑

Dry Run Walkthrough

Input: Push values 10, 20, then pop one value

Goal: Show how the stack changes after pushing two values and popping one

Step 1: Push 10 onto empty stack

Top -> [10] -> null
       ↑

Why: We add the first item, so top points to this new node

Step 2: Push 20 onto stack

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

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

Step 3: Pop top value (20) from 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 Javascript

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

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

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top; // new node points to current top
    this.top = newNode; // top moves to new node
  }

  pop() {
    if (this.top === null) {
      return null; // stack empty
    }
    const poppedValue = this.top.value;
    this.top = this.top.next; // top moves down one node
    return poppedValue;
  }

  print() {
    let curr = this.top;
    let result = '';
    while (curr !== null) {
      result += curr.value + ' -> ';
      curr = curr.next; // move to next node
    }
    result += 'null';
    console.log(result);
  }
}

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

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

link new node to current top to keep stack order

this.top = newNode; // top moves to new node

update top pointer to new node for push

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

handle pop on empty stack safely

this.top = this.top.next; // top moves down one node

remove top node by moving top pointer down

curr = curr.next; // move to next node

traverse stack nodes for printing

Output

20 -> 10 -> null

10 -> null

Popped value: 20

Complexity Analysis

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

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

vs Alternative: Compared to using an array, linked list avoids resizing and shifting elements, making push/pop always O(1)

Edge Cases

Pop from empty stack

Returns null safely without error

DSA Javascript

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

Push single element

Stack top points to the new single node

DSA Javascript

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

When to Use This Pattern

When you need last-in-first-out (LIFO) behavior with efficient add/remove at one end, use a stack implemented with a linked list for constant time operations.

Common Mistakes

Mistake: Not updating the top pointer after push or pop
Fix: Always assign this.top to the new node after push and to this.top.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 top node.

Use when you want a stack with dynamic size and fast push/pop operations.

The key is to always update the top pointer to add or remove the top element efficiently.

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