Intro to Linked Lists via JavaScript - Part 2: Implementation

Back in Part 1 we got a birds-eye look at what linked lists are and why they’re necessary for creating more advanced data structures. Now we can learn how to start implementing a fully-featured doubly linked list in JavaScript.

Singly linked lists and implementations in other data structures will generally just be more barebones versions of what we’ll cover here, so this would be good to bookmark as a general reference.

Structure

Like any other class, we can store whatever we want in each node, the only important parts are the next and prev pointers, which should be null by default.

Likewise the only things our list needs are its tail, head, and length. We’ll need to manually manipulate the length since, unlike arrays, it won’t be calculated for us and will be necessary for searching for items.

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

class linkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  };
};

Create

Now we can start setting up all of our methods inside our linkedList class. Since we don’t have any of our normal goodies like push or shift we’ll have to create our own versions.

Head and Tail

Most of our operations are based more on manipulating the pointers in the surrounding nodes than on the item we want to change. To add something isn’t just shoving a new node where we want, like with an array, but changing the pointers on the items before or after to point to our new item, then manually incrementing the list’s length.

If there isn’t anything in the list, we want to set the new item as both the head and tail, since it’s the only item. To add or remove from the end of the list we’ll take the current head/tail we want to replace and set its pointer to our new item or null, change the list’s head/tail to our new node or null, then increment the length.

addHead(val) {
  let newNode = new Node(val);

  if (!this.head) {
    this.head = newNode;
    this.tail = this.head;
  };

  this.head.prev = newNode;
  newNode.next = this.head;
  this.head = newNode;

  this.length++;
  return this;
}

addTail(val) {
  let newNode = new Node(val);

  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  };

  this.tail.next = newNode;
  newNode.prev = this.tail;
  this.tail = newNode;

  this.length++;
  return this;
}

removeHead() {
  let removed = this.head;
  if (!this.head) return undefined;

  this.head = this.head.next;
  this.head.prev = null;

  this.length--;
  return removed;
}

removeTail() {
  let removed = this.tail;
  if (!this.tail) return undefined;

  if (this.length === 1) {
    this.head = null;
    this.tail = null;
  };

  this.tail = removed.prev;
  this.tail.next = null;

  this.length--;
  return removed;
}

Find

Since we don’t have an index to get our item by we’re going to have some problems with inserting/removing in the middle of the list, so we’re going to need our own utility function.

It’s very simple, we just need to store the current item and use a for or while loop to use our pointers to update current until we’re at the item we want.

Graphic/Animation thanks to VisuAlgo.net

Of course, this gives us an O(n) search time, but since we’re using a doubly linked list we can just start from the tail if what we want is past the middle of the list, giving us O(n / 2).

find(index) {
  let current
  if (index < 0 || index >= this.length) return undefined;

  if (index <= this.length / 2) {
    current = this.head;
    for (let i = 0; i < index; i++) current = current.next;
  } else {
    current = this.tail;
    for (let i = this.length; i > index; i--) current = current.prev;
  }

  return current;
}   

Insert and Remove

Now that we have our little utility in place we can use it to find the item in the index we want then set the pointers on it and the item before and after it to our new node, thus “stitching” it into place.

Graphic/Animation thanks to VisuAlgo.net

If the index is on the head or tail, we can just reuse our previous methods.

insert(val, index) {
  if (index < 0 || index > this.length) return null;
  if (index === this.length) return this.addTail(val);
  if (index === 0) return this.addHead(val);

  let prev = this.find(index - 1),
      newNode = new Node(val),
      temp = prev.next;

  prev.next = newNode;
  newNode.next = temp;
  newNode.prev = prev;

  this.length++;
  return true;
}

Removing is obviously just the inverse of inserting and a bit simpler. Find the node we want to remove and set the pointers on the surrounding nodes to each other, leaving nothing that references the removed node.

Graphic/Animation thanks to VisuAlgo.net

remove(index) {
  if (index < 0 || index >= this.length) return null;
  if (index === this.length) return this.removeTail();
  if (index === 0) return this.removeHead();

  let removed = this.find(index);

  removed.prev.next = removed.next;
  removed.next.prev = removed.prev;

  this.length--;
  return removed;
}

Update

This one is so simple it’s almost no even worth mentioning, just find the item and reset it’s value.

update(val, index) {
  let node = this.find(index);
  if (node) node.val = val;
  return node;
}

Conclusion

While this may have seemed like a lot of work, it’s good to keep in mind that in many cases you won’t need all of it.

I really recommend checking out Buckets.js for when you don’t feel like manually making one, although it’s always good to understand the concept on a deeper level.