Implement a Stack with a Singly Linked List

First In, Last Out

A stack is a data structure that follows the First In, Last Out (FILO) principal. You can think of this like a stack of plates. As you put plates away, each one goes on top of the one before. As you pull them out, you take the plate from the top of the stack, which is the one that was most recently added. Stacks are useful in many instances. For example, the browser's call stack is a stack. The ability to undo and redo (like in PhotoShop) is also commonly implemented using stacks.

Native Data Structures

JavaScript does not include a native stack structure. You can use the built-in JavaScript array to mock a stack, relying on its push and pop methods for O(1) insertion and removal. However, there can be drawbacks to this method. Using an array requires extra memory for storing indices for each element. There is also the possibility that the location in memory where your array is stored runs out of space, requiring full re-indexing of the entire array in order to add one element.

Implement with a Singly Linked List

In order to implement a stack with a linked list, you can create a Node class where each element of the stack is a node. Each node should have a value property and a pointer to the next node:

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

Next, you can create a Stack class, which is simply a Linked List that we've named Stack. In this example, we'll use properties of head and size:

class Stack {
  constructor() {
    this.head = null;
    this.size = 0;
  }
}

Required Methods

The two most important methods to add to our Stack are push and pop.

Push

push accepts a value as an argument, and adds that value to the top of the stack. In practice that means, creating a new node using the value passed in, updating the head value on our stack to point to the new node, and incrementing the stack's size:

class Stack {
  ...

  push(val) {
    const newNode = new Node(val)
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
    return this;
  }

}

Pop

pop is nearly the inverse of push. It will remove the most recently added node in our stack and return it. In this case, that means removing the existing head node, updating that head's next node to become the new head node, and decrementing the size. We'll also remove the old head's pointer into the list to avoid any accidental look-up abilities:

class Stack {
  ...

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

    const oldHead = this.head;
    this.head = oldHead.next;
    oldHead.next = null;
    this.size--;
    return oldHead;
  }

}

Additional Methods

Some other methods that are commonly added include peek, isEmpty, and size.

Peek

peek returns the top element on the stack, without removing it, allowing us to "peek" into the stack:

class Stack {
  ...

  peek() {
    return this.head;
  }
}

isEmpty

isEmpty returns a boolean - true if the stack is empty or false if not:

class Stack {
  ...

  isEmpty() {
    return !!this.size;
  }
}

size

size returns the size of the stack:

class Stack {
  ...

  size() {
    return this.size;
  }
}