Implementing a Doubly Linked List in JavaScript

25 Apr 2021 •

In this article, we will implement a common data structure called a Linked List (specifically a Doubly Linked List) using JavaScript.

The Setup

We will create a constructor function called LinkedList. We will also create a helper constructor called Node to represent each item in the list.

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

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

A Node stores three pieces of information:

1. Value: The data stored in the node.
2. Next: A pointer to the next node in the list.
3. Prev: A pointer to the previous node in the list.

The LinkedList itself tracks the head (start) and tail (end) of the list.

---

1. Adding to the Head (addToHead)

This method adds a new node to the beginning of the list.

LinkedList.prototype.addToHead = function (value) {
  // Create a new node. It becomes the new head, so its 'next' is the old head.
  var newNode = new Node(value, this.head, null);

  if (this.head) {
    // If a head already exists, link it back to the new node
    this.head.prev = newNode;
  } else {
    // If the list was empty, this node is both head and tail
    this.tail = newNode;
  }
  
  // Update the head pointer to the new node
  this.head = newNode;
};

How it works: We create newNode. Since it will be the first item, its next property points to the current this.head. Its prev property is null. If the list was empty, this node is also the tail. Finally, we update this.head to point to our new node.

---

2. Adding to the Tail (addToTail)

This method adds a new node to the end of the list.

LinkedList.prototype.addToTail = function (value) {
  // Create a new node. Its 'prev' is the current tail.
  var newNode = new Node(value, null, this.tail);

  if (this.tail) {
    // If a tail exists, point it to the new node
    this.tail.next = newNode;
  } else {
    // If list is empty, this node is also the head
    this.head = newNode;
  }

  // Update the tail pointer
  this.tail = newNode;
};

---

3. Removing the Head (removeHead)

Removes the first node and returns its value.

LinkedList.prototype.removeHead = function () {
  // Case 1: List is empty
  if (!this.head) return null;
  
  var val = this.head.value;
  
  // Move head pointer to the next node
  this.head = this.head.next;

  if (this.head) {
    // If there is still a node left, remove its reference to the old head
    this.head.prev = null;
  } else {
    // Case 2: List is now empty, so tail must also be null
    this.tail = null;
  }
  
  return val;
};

---

4. Removing the Tail (removeTail)

Removes the last node and returns its value.

LinkedList.prototype.removeTail = function () {
  // Case 1: List is empty
  if (!this.tail) return null;
  
  var val = this.tail.value;
  
  // Move tail pointer to the previous node
  this.tail = this.tail.prev;

  if (this.tail) {
    // If there is a node left, remove its reference to the old tail
    this.tail.next = null;
  } else {
    // Case 2: List is now empty, so head must also be null
    this.head = null;
  }
  
  return val;
};

---

5. Searching (search)

Finds a value in the list.

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

Time Complexity: O(n) - We might have to traverse the entire list.

---

6. Finding Indexes (indexOf)

Returns all indexes (positions) of a 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;
};

---

Putting it all together

Here is the full source code for our Doubly Linked List:

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;
};