Doubly Linked List in JavaScript

A doubly linked list is a collection of nodes where each node contains a value, one reference (or pointer) to the next node in the sequence and one reference to the previous node. The list itself maintains a reference to the first node head and the last node tail, and it keeps track of the number of nodes, length.

Theory

Arrays and objects are excellent data structures for most applications. However, when you start dealing with large datasets (in the order of hundreds of thousands or more) having the right data structure becomes crucial.

And doubly linked lists same as a singly linked lists are particularly useful when you require a lot of insertion and deletion at the start or the end of your data.

So you might ask what's the difference between a singly and doubly linked list well singly linked list is a list where each node is linked by the next property which as the name suggests stores the next element. While a doubly linked list has his nodes storing the next and the previous node which makes it easier to iterate over as it allows us to start from both sides of the list depending on the querying index but we'll come back to that soon enough!

So, as you probably guessed it the big difference is the memory, if you're in a memory sensitive environment and you insert only at the beginning use a singly linked list (more details in my singly linked list guide) otherwise let me tell you how great doubly linked list are!

Implementation

Node Class

Now that we've talked about the why and the when I guess we should go into the how.

First, let's define the Node class, which will represent each element in the linked list.

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

DoublyLinkedList Class

Next, we'll define the DoublyLinkedList class, which will manage the nodes and provide methods to manipulate the list.

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

Adding a Node to the End

function push(value) {
  const new_node = new Node(value);
  if (this.length === 0) {
    this.head = new_node;
    this.tail = this.head;
  } else {
    new_node.prev = this.tail;
    this.tail.next = new_node;
    this.tail = new_node;
  }

  this.length++;
  return this;
}

Explanation: The push method creates a new node with the given value. If the list is empty, we set both the head and tail to the new node.Otherwise, we set the new node's prev property to be the tail before appending the new node to the end of the list by updating the next property of the current tail and then setting the new node as the tail. The length is incremented, and the updated list is returned.

Removing a Node from the End

function pop() {
  if (!this.head) return undefined;
  const removed = this.tail;
  if (this.length === 1) {
    this.head = null;
    this.tail = null;
    this.length--;
    return removed;
  }

  this.tail = this.tail.prev;
  this.tail.next = null;
  this.length--;
  return removed;
}

Explanation: The pop method first checks if the list is empty and returns undefined if it is. We save the current tail as removed before modifying the list. If there is only one item, we set both head and tail to null and return it. Otherwise, we take the tail's previous node, set it as the new tail, and clear its next pointer — this is where the doubly linked list fulfills the singly linked list's shortcoming: no traversal needed to find the second-to-last node.

Removing a Node from the Beginning:

As for array, the shift method is used to remove a node from the beginning of the list. Unlike with arrays this process doesn't involves reassigning every node's index so here it's pretty much where linked list excels:

function shift() {
  if (!this.head) return undefined;
  const current_head = this.head;
  this.head = this.head.next;
  this.length--;
  if (this.length === 0) {
    this.tail = null;
  }
  return current_head;
}

See how few operations there are?

Explanation: We first check if the list is empty and return undefined if it is. Otherwise, we store the head before overriding it with its next node then we decrement the length and finally we return the node we removed. Also don't forget to clean up the tail if there is no more items as we only took care of the head by setting it to current_head.next which is null when there is only one element.

Adding a Node to the Beginning

Next stop unshift, the opposite of shift, adding a new node to the beginning of the list, again this is where linked list excel, let's see how:

function unshift(value) {
  let new_node = new Node(value);
  if (!this.head) {
    this.head = new_node;
    this.tail = this.head;
  } else {
    new_node.next = this.head;
    this.head.prev = new_node;
    this.head = new_node;
  }

  this.length++;
  return this;
}

Explanation: Quite simple again, we create a new node with the given value. If the list is empty, we set both the head and tail to the new node. Otherwise, we set the next property of the new node to be the current head before setting the head's prev property to be the head and finally we update the head to be the new node. The length is incremented, and the updated list is returned.

Getting a Node by Index:

How about the get method? With arrays we can easily get an item by its index arrindex but with a linked list it's a little harder as nodes are not referenced by index, they're like free agents linked to each other.

function get(index) {
  if (this.length === 0 || this.length <= index || index < 0) return undefined;
  const mid_index = Math.floor(this.length / 2);
  let item;
  if (index > mid_index) {
    item = this.tail;
    for (let i = 0; i < index; i++) {
      item = item.prev;
    }
  } else {
    item = this.head;
    for (let i = 0; i < index; i++) {
      item = item.next;
    }
  }

  return item;
}

Explanation: Because nodes are not indexed we need to traverse the whole list to find our node and to prevent our traversal to run out of the list we need a guard clause, returning undefined if the index parameter is out of bounds. Otherwise we will define a variable called mid_index which allows us to determine if we need to start looping from the head going from item.next to item.next (which will be returned if the index parameter is 0) or from the tail going from item.prev to item.prev until the index parameter is superior or inferior to the current iterator i meaning our item variable is currently storing the desired item.

Setting a Node Value by Index

function set(index, value) {
  const item = this.get(index);
  if (!item) return false;
  item.value = value;
  return true;
}

Explanation: Here it's quite simple we use our previously defined get method to find the item, if the item is undefined we return false otherwise we update the value of the item and return true.

Inserting a Node at a Specific Index:

function insert(value, index) {
  if (index >= this.length) return !!this.push(value);
  else if (index === 0) return !!this.unshift(value);
  const next_item = this.get(index);
  if (!next_item) return false;

  const new_item = new Node(value);
  const previous_item = next_item.prev;
  previous_item.next = new_item;
  next_item.prev = new_item;
  new_item.prev = previous_item;
  new_item.next = next_item;
  this.length++;
  return true;
}

Explanation: Let's recap, there are a few scenarios we need to handle :

• First if the index parameter superior or equal to the length it means we want to insert at the end so we can just use the push function.
• Second if the index parameter is equal to 0 it means we want to insert at the beginning so we just use the unshift function.

Otherwise we get the item with our get function, in case the index is incoherent it will return undefined so we return false, but if we have something it's the node that will become the next_item from there we need to store it's previous item. Now we have everything needed to set the new item between the previous_item and the next_item:

• we set previous.next and next_item.prev to be our new_node
• we set the next and prev property on the new_item to be be next_item and previous_item respectively.

Removing a Node at a Specific Index

function remove(index) {
  if (index === 0) return this.shift();
  else if (index === this.length - 1) return this.pop();
  const item = this.get(index);
  if (!item) return undefined;
  const previous = item.prev;
  const next = item.next;
  previous.next = next;
  next.prev = previous;
  this.length--;
  return item;
}

Explanation: So here again we have some edge cases to handle the first one is if the provided index is 0 then we can reuse our shift function which does just that, another case is if the index is equal to the length - 1 it means we want to remove the last item so we reuse our pop function.

From there if we didn't return yet it means for any node but the tail or the head so we use our get function to get the item we want to remove if we don't get it we return undefined. Otherwise we define a previous and a next value. Now that we have both it's quite easy we essentially break the link by setting the previous.next to be the next property to be the next property of the item we are removing and we do the same for next.prev. Once done we to decrease the length and return the item we removed.

Reversing the List:

Last but not least, the reverse function, this one is totally optional and is mostly good to know for interviews as it could randomly show up.

function reverse() {
  let temp = null;
  let current = this.head;

  while (current != null) {
    temp = current.prev;
    current.prev = current.next;
    current.next = temp;
    current = current.prev;
  }

  if (temp != null) {
    this.head = temp.prev;
  }

  return this;
}

This is though one so I'll try my best to guide you through:

We first define two variables, current variable which holds the element we are currently looping over starting from the head and temp which will hold the prev variable before we override it.

Now that we have everything set up we will simply loop until we have a current variable, inside the loop we essently swap the next and prev properties for all nodes. Last but not least we need to set the head to be temp.prev as temp always holds the previous item we iterated over but before we need to and if statement to handle the case where the list has only 1 node or is empty.

Performance considerations

• Insertion: O(1) for push and unshift, O(n) for insert (remember we have to traverse the list unless inserting at the beginning or end).
• Removal: O(1) for pop and shift, O(n) for remove (remember we have to traverse the list unless removing from the beginning or end).
• Search: O(n), we still have to traverse the list
• Access: O(n), we still have to traverse the list

Practical Use Cases

• Frequent Insertions/Deletions: Doubly linked lists are ideal when you need to frequently insert or delete elements at both the beginning and end of the list, as well as in the middle.
• Dynamic Size: Doubly linked lists can easily grow or shrink in size, making them suitable for applications where the size of the data structure is not known in advance.
• Bidirectional Traversal: The ability to traverse in both directions makes doubly linked lists useful for applications requiring navigation in both forward and backward directions.
• Memory Management: In lower-level languages, doubly linked lists allow for storing memory in a non-contiguous way, which can be more efficient in certain scenarios.

Example use cases

• Browser History: Managing the history of visited web pages where new pages are added to the end and users can navigate both forward and backward through their history.
• Music Playlist: Managing a playlist where songs can be added or removed from both the beginning and end, and users can navigate through the playlist in both directions.
• Undo/Redo Functionality: Implementing undo and redo operations in applications like text editors or graphic design software, where users need to move back and forth between states.
• Navigation Systems: Used in applications requiring bidirectional navigation, such as in-file system navigation or game state management.

Congrats 🎉 you made it through I hope you learned a lot, I certainly did and if you have any suggestions, improvements or anything that comes to your mind don't hesitate to write! I'll reply as soon as possible!

Happy coding! 🚀