Back to Open Book Shelf

Implement a Stack with a Singly Linked List

In this assignment, your goal is to implement a stack using a singly linked list. We'll provide you with a template to help you get started. You might recognize the class ListNode from the Linked List assignment. We encourage you to implement the stack independently but feel free to reference our walkthrough if you need guidance.

Problem Description

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class Stack {
  constructor() {
    this.top = null;
  }
  peek() {
    // Returns the value of the top most element without removing it.

    // If the stack is empty, it returns `null`.
  }

  push(value) {
    // Adds an item to the stack
  }

  pop() {
    // Removes the item from the stack and returns it

    // If the stack is empty, it returns `null`.
  }
}

const myStack = new Stack();
myStack.push(1);
console.log('Top element:', myStack.peek());  // logs 'Top element: 1'
myStack.push(2);
console.log('Top element:', myStack.peek());  // logs 'Top element: 2'
myStack.push(3);
console.log('Top element:', myStack.peek());  // logs 'Top element: 3'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 2'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 1'
myStack.pop();
console.log('Peek on empty stack:', myStack.peek());    // logs 'Peek on empty stack: null'

Walkthrough & Solution

Let's start with the easiest method, peek. This method returns the topmost node's value or null if the stack is empty.

// some code above

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

In our solution, we use a ternary operator. If the top element exists, this.top.val will be returned; otherwise, null. We could rewrite it with an if statement as well:

// some code above

peek() {
  if (this.top) {
    return this.top.val;
  }
  return null;
}

The push method is a bit more involved.

  • First, given a value, we want to create a ListNode with that value, referenced by newNode.
  • Next, we must consider two scenarios: an empty stack and a non-empty stack.
    • If the stack has no elements, directly assign newNode as the top node.
    • If the stack is not empty:
      • Set the next property of newNode to point to the current top node.
      • Update the top pointer to reference newNode.

Assuming we have created a stack, let's see how adding the first three elements would look visually:

myStack.push(1)

myStack.push(2)

myStack.push(3)

// some code above

push(value) {
  const newNode = new ListNode(value);
  if (!this.top) {
    this.top = newNode;
  } else {
      newNode.next = this.top;
      this.top = newNode;
  }
}

We can simplify this implementation significantly. Remember that our ListNode class allows us to pass in a next value when we create a new node. As a result, we can assign the current top to our new node's next value, handling both scenarios with one action:

// some code above

push(value) {
  this.top = new ListNode(value, this.top);
}

If the stack is empty, this.top is null, which is the default value that ListNode uses when we don't pass in a next argument. If the stack is not empty, this.top references the node that should be referenced by newNode's next pointer:

The pop method returns null if the stack is empty, otherwise it returns the topmost node. This means that we need to keep a reference to this top node to return its value later.

Let's first see how popping elements from the stack would look visually. We'll continue where we left off in the previous image, with the stack containing three elements.

myStack.pop()

myStack.pop()

myStack.pop()

myStack.pop()

// some code above

pop() {
  if (!this.top) return null;

  const poppedNode = this.top;

  this.top = this.top.next;

  return poppedNode.val;
}

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

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

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

  push(value) {
    this.top = new ListNode(value, this.top);
  }

  pop() {
    if (!this.top) return null;

    const poppedNode = this.top;

    this.top = this.top.next;

    return poppedNode.val;
  }
}

const myStack = new Stack();
myStack.push(1);
console.log('Top element:', myStack.peek());  // logs 'Top element: 1'
myStack.push(2);
console.log('Top element:', myStack.peek());  // logs 'Top element: 2'
myStack.push(3);
console.log('Top element:', myStack.peek());  // logs 'Top element: 3'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 2'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 1'
myStack.pop();
console.log('Peek on empty stack:', myStack.peek());    // logs 'Peek on empty stack: null'
Previous:  Stacks
Next:  Queues