Stack Implementation Using Linked List in DSA Javascript - 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 a stack using a linked list to store these actions.

🎯 Goal: Build a stack data structure using a linked list in JavaScript. You will create nodes, push actions onto the stack, pop actions from the stack, and finally print the current stack state.

📋 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(value) method to add a node on top

Implement pop() method to remove and return the top node's value

Implement printStack() method to print stack values from top to bottom

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, browser history, and expression evaluation.

💼 Career

Understanding stack implementation helps in coding interviews and building efficient algorithms.

1

Create Node and Stack Classes

Create a class called Node with a constructor that takes value and sets this.value and this.next to null. Then create a class called Stack with a constructor that sets this.top to null.

DSA Javascript

class Node {
  // Your code here
}

class Stack {
  // Your code here
}

Hint

Think of Node as a box holding a value and a pointer to the next box. The Stack starts empty with top as null.

2

Add push Method to Stack

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

DSA Javascript

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

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

  // Your code here
}

Hint

Remember, pushing means putting the new node on top and linking it to the previous top.

3

Add pop Method to Stack

Inside the Stack class, add a method called pop that removes the top node and returns its value. If the stack is empty (top is null), return null. Otherwise, save the current top node, update top to top.next, and return the saved node's value.

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;
    this.top = newNode;
  }

  // Your code here
}

Hint

Pop means removing the top node and returning its value. If empty, return null.

4

Add printStack Method and Test Stack

Inside the Stack class, add a method called printStack that prints the stack values from top to bottom separated by ' -> ' and ending with 'null'. Then create a stack object, push the values 'Action1', 'Action2', and 'Action3' onto it in that order. Pop one value from the stack. Finally, call printStack() to display the current stack.

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;
    this.top = newNode;
  }

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

  // Your code here
}

// Your code here

Hint

Print each node's value from top to bottom, separated by ' -> ', ending with 'null'. Push three actions, pop one, then print.

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