Implementation of linked list in JavaScript

25 Apr 2021 10 mins

In the article, we will implement commonly know data structure call Linked List using javascript.

Let’s create a function call LinkedList which is a constructor function. Also we will add new constructor function for Node .

function LinkedList() {
  /*code */
}
function Node() {
  /*code */
}

Cool, LinkedList and Node will have certain properties. For each node, we want to store following information:

1. value,
2. next node,
3. previous node.

So, we need these three attributes in our Node constructor. Whereas, LinkedList have two property head node and tail node. Let’s implement it.

function LinkedList() {
  this.head = null;
  this.tail = null;
}
function Node(value, next, prev) {
  this.next = next;
  this.value = value;
  this.prev = prev;
}

---

Adding head to method:

// constructor code above
LinkedList.prototype.addToHead = function (value) {
  // we have made a new node.
  var newNode = new Node(value, this.head, null);
  // Attaching it to head node.
  if (this.head) {
    this.head.prev = newNode;
  } else {
    /**
     * little confusing :) if this.head is null then its
     * the only node in the linked list. So both head
     * and tails should point to same node.
     */
    this.tail = newNode;
  }
  // finally, we need to add new node to our linked list
  // we do this in both situation.
  this.head = newNode;
};

In above code, we can add new node to head of our linked list . In the above function, we have one argument which is value. Then in the body of our function we create a new node and pass a value as the first parameter. Second parameter which is pointer to next node will be current node which can be access using this.head. For head node previous pointer will always be null so, we will pass null as third parameter.

Attaching it to head node:

We need to handle two different cases here. If linked list is empty, both head and tail node will be null. For this case we will assign new node to this.head and tail node will be null. Second case, list is not empty, we have to assign new node as head node, and assign current head node to this.prev for our new node.

---

Add to tail method:

// constructor code above

LinkedList.prototype.addToTail = function (value) {
  var newNode = new Node(value, null, this.tail);
  /**
   * handling the case where Linked list is empty.
   */
  if (this.tail) this.tail.next = newNode;
  else this.head = newNode;

  // assign newNode to tail
  this.tail = newNode;
};

Similar to addToHead method, we take value as an argument and next value for tail node will be empty whereas previous node will be current linked list tail.

---

Removing Head and Tail Node:

// ...above constructors code

LinkedList.prototype.removeHead = function () {
  if (!this.head) return null;
  let val = this.head.value;
  this.head = this.head.next;
  if (this.head) this.head.prev = null;
  else this.tail = null;
  return val;
};

LinkedList.prototype.removeTail = function () {
  if (!this.tail) return null;
  let val = this.tail.value;
  this.tail = this.tail.prev;
  if (this.tail) this.tail.next = null;
  else this.head = null;
  return val;
};

In above methods, fist we check if head/tail node exist. In case of null, we will return null. This case will be true if Linked List is empty.

If head/tail is not empty, we assign this to variable call val, after that previous value (in case of tail) store in that node is assigned as new tail node also next is set to null since next pointer in tail node is empty.

In case of head node, next node point assign to current head will be new head node and prev value of that next head will be null.

---

Search for the value in Linked List:

LinkedList.prototype.search = function (searchValue) {
  var currentNode = this.head;
  while (currentNode) {
    if (currentNode.value === searchValue) return currentNode.value;
    currentNode = currentNode.next;
  }
  return null;
};

// similar approach to calculate indexOf value
LinkedList.prototype.indexOf = function (value) {
  var indexes = [];
  var currentIndex = 0;
  var currentNode = this.head;
  while (currentNode) {
    if (currentNode.value === value) indexes.push(currentIndex);
    currentNode = currentNode.next;
    currentIndex++;
  }
  return indexes;
};

For searching through linked list, we run a while loop checking for value starting for head node. We will be inside while loop until we found result or we encounter end tail of the linked list. If any node with next assigned as null is tail node. Complexity of this search function is Big O(n).

---

Putting it all together:

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

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

LinkedList.prototype.addToHead = function (value) {
  var newNode = new Node(value, this.head, null);
  if (this.head) this.head.prev = newNode;
  else this.tail = newNode;
  this.head = newNode;
};

LinkedList.prototype.addToTail = function (value) {
  var newNode = new Node(value, null, this.tail);
  if (this.tail) this.tail.next = newNode;
  else this.head = newNode;
  this.tail = newNode;
};

LinkedList.prototype.removeHead = function () {
  if (!this.head) return null;
  var val = this.head.value;
  this.head = this.head.next;
  if (this.head) this.head.prev = null;
  else this.tail = null;
  return val;
};

LinkedList.prototype.removeTail = function () {
  if (!this.tail) return null;
  var val = this.tail.value;
  this.tail = this.tail.prev;
  if (this.tail) this.tail.next = null;
  else this.head = null;
  return val;
};

LinkedList.prototype.search = function (searchValue) {
  var currentNode = this.head;
  while (currentNode) {
    if (currentNode.value === searchValue) return currentNode.value;
    currentNode = currentNode.next;
  }
  return null;
};

LinkedList.prototype.indexOf = function (value) {
  var indexes = [];
  var currentIndex = 0;
  var currentNode = this.head;
  while (currentNode) {
    if (currentNode.value === value) indexes.push(currentIndex);
    currentNode = currentNode.next;
    currentIndex++;
  }
  return indexes;
};