Beginner's guide to Linked List in JavaScript

There are a few different types of linked lists. But the most popular ones are: singly, doubly and circular. In this article we will learn to implement a doubly Linked List Data structure in JavaScript. Some of the operations that we are going to implement in this article are:

1. Add a node to the head
2. Add a node to the tail
3. Reverse a linked list

We will start by creating a linked list function constructor and it will contain two piece of information (a) the head and (b) the tail.

All a linked list class needs are two pointers the head pointer which points to the first
node in the list and the tail pointer which points to the last node in the list.

function LinkedList() {
  this.head = null;
  this.tail = null;
}

Initially the head and the tail will be set to null because they will have no nodes to point at the start.

Next, for our node list we will create a node constructor function. Each node will have three properties on the them (a) the value, (b) the pointer to the next node and (c) the pointer to the previous node.

function Node(value, next, prev) {
    this.value = value;
    this.next = next;
    this.prev = prev
}

Now we will instantiate a new linked list.

const LL = new LinkedList()

// if you try to access the linked list, it will look like this
console.log(LL) // { head: null, tail: null }

Next up, the new instantiation will have few helper method to add and remove data.

1. addToHead

This method adds new value to head of the linked list.

LinkedList.prototype.addToHead = function (value) {
  // instantiate  a new node
  const newNode = new Node(value, this.head, null);

  // if there is already a head present set its prev value to the newNode

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

  // set the current head to newNode
  this.head = newNode;
};


LL.addToHead(80)
LL.addToHead(90)
LL.addToHead(100)

2. addToTail

This method adds new value to tail of the linked list.

LinkedList.prototype.addToTail = function (value) {
  const newNode = new Node(value, null, this.tail);

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

  this.tail = newNode;
};

3. removeHead

This method deletes the current head and returns its value

LinkedList.prototype.removeHead = function () {
  // if there is no head, simply return null
  if (!this.head) return null;
  // else

  // store the current head value in a variable to return it later
  let currentVal = this.head.value;

  // now  reassign the current head
  this.head = this.head.next;

  // if there is a next value, change its prev value to null
  if (this.head) {
    this.head.prev = null;
  } else {
    this.tail = null;
  }

  return currentVal;
};

4. removeTail

This method deletes the current tail and returns its value

LinkedList.prototype.removeTail = function () {
  if (!this.tail) return null;

  let currentVal = this.tail.value;

  this.tail = this.tail.prev;

  if (this.tail) {
    this.tail.next = null;
  } else {
    this.tail = null;
  }

  return currentVal;
};

5. reverse

This method reverses the linked list

LinkedList.prototype.reverse = function () {
  // head is the first node in the list

  let currentNode = this.head;

  //  start with the head

  // as long as currentNode has a value run the loop

  while (currentNode) {
    //  store the current node prev value in a varialbe
    let temp = currentNode.prev;
    //  swap the previous and next node with each other
    currentNode.prev = currentNode.next;
    currentNode.next = temp;

    //  assing the previous node value to the current node which will eventually be null
    currentNode = currentNode.prev;
  }

  // store the currentTail's value in a variable

  let currentTail = this.tail;

  // reassign the tail's value to current head and head's value to previous tail
  this.tail = this.head;
  this.head = currentTail;
};

Summary

In this article we implemented a doubly linked list in JavaScript. Hope you enjoyed reading it.:)