Master How Doubly Linked List is implemented in JavaScript

Hi 👋, welcome back. It's been exactly 6 days since we started this journey together. I want to believe it has been an awesome experience. Yesterday, we learned about Singly Linked Lists, how to implement them in JavaScript with a few basic operations. Today, we'll learn how to implement Doubly Linked Lists in JavaScript. So, let's dive in! 🏊‍♂️

Course Outline

1. Introduction
2. Implementing Doubly Linked Lists
   • Creating the Node class
   • Insert at the beginning
   • Insert at the end
   • Insert at a specific position
   • Delete a node
   • Traverse forward
   • Traverse backward
   • Search for a node
3. Usage Example
4. Conclusion

Introduction

When it comes to data structures, the Doubly Linked List is a versatile and powerful tool. 🛠️ It's a type of linked list where each node contains a data field and two pointers, one pointing to the next node and the other pointing to the previous node. This bidirectional traversal capability makes doubly linked lists particularly useful in various programming scenarios like:

• Implementing queues or stacks with efficient insertion and deletion.
• Implementing undo/redo functionality in applications. ↩️↪️
• Implementing browser's forward and back button. 🔙🔜
• Implementing music players' next and previous song feature. 🎵⏮️⏭️
• Implementing LRU (Least Recently Used) cache.

Implementing Doubly Linked Lists

A doubly-linked list is like a singly-linked list, but with an extra feature: you can move in both directions. This means you can go from the start to the end of the list. In the next section, we'll learn how to implement a doubly-linked list in JavaScript. 🚀

By the way, if you missed the previous article on singly-linked lists, you could check it out below 👇

How to Implement Singly Linked List in JavaScript

Emmanuel Ayinde ・ Oct 4

#javascript #beginners #programming #dsa

As we already know from last article, we'll need to create a Node class to represent each element in the list. This is similar to what we did in the previous article except that we'll need to add a prev property to the Node class to keep track of the previous node (which is the exact feature that makes a doubly-linked list different from a singly-linked list).

Creating the Node class

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

This is a simple visualization of what we've just created.

Now that we have our Node class, let's implement the DoublyLinkedList class.

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

  // Methods will be implemented here 👇
}

• Explanation: The constructor initializes the list with head and tail set to null, indicating that the list is empty. The length property is initialized to 0, representing the number of nodes in the list.

Now that we have our DoublyLinkedList class, let's start implementing our methods.

Insert at the beginning

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

  insertAtBeginning(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.length++;
  }

  // Other methods will be implemented here 👇
}

• Explanation: This method inserts a new node at the beginning of the list.
  • A new node is created with the provided data.
  • If the list is empty (!this.head), both head and tail are set to the new node.
  • If the list is not empty, the new node's next pointer is set to the current head, and the current head's prev pointer is updated to point to the new node. Finally, the head is updated to the new node.
  • The length of the list is incremented (since we add to the list).

Insert at the end

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

  // Previous methods  here 👇
  // .
  // .
  // .

  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // Other methods will be implemented here 👇
}

• Explanation: This method inserts a new node at the end of the list.
  • A new node is created with the provided data.
  • If the list is empty (!this.tail), both head and tail are set to the new node.
  • If the list is not empty, the new node's prev pointer is set to the current tail, and the current tail's next pointer is updated to point to the new node. Finally, the tail is updated to the new node.
  • The length of the list is incremented.

Insert at a specific position

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

  // Previous methods here 👇
  // .
  // .
  // .

  // Insert at a specific position
  insertAtPosition(data, position) {
    if (position < 0 || position > this.length) {
      return false; // Invalid position
    }
    if (position === 0) {
      this.insertAtBeginning(data);
      return true;
    }
    if (position === this.length) {
      this.insertAtEnd(data);
      return true;
    }
    const newNode = new Node(data);
    let current = this.head;
    for (let i = 0; i < position - 1; i++) {
      current = current.next;
    }
    newNode.next = current.next;
    newNode.prev = current;
    current.next.prev = newNode;
    current.next = newNode;
    this.length++;
    return true;
  }

  // Other methods will be implemented here 👇
}

• Explanation: This method inserts a new node at a specified position in the list.
  • It first checks if the position is valid (between 0 and this.length).
  • If the position is 0, it calls insertAtBeginning. If the position is equal to this.length, it calls insertAtEnd.
  • For other positions, a new node is created, and the method traverses the list to find the node just before the specified position.
  • The new node's pointers are set accordingly, and the length is incremented.

Delete a node

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

  // Previous methods here 👇
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return false;
    let current = this.head;
    while (current) {
      if (current.data === data) {
        if (current === this.head && current === this.tail) {
          this.head = null;
          this.tail = null;
        } else if (current === this.head) {
          this.head = current.next;
          this.head.prev = null;
        } else if (current === this.tail) {
          this.tail = current.prev;
          this.tail.next = null;
        } else {
          current.prev.next = current.next;
          current.next.prev = current.prev;
        }
        this.length--;
        return true;
      }
      current = current.next;
    }
    return false; // Node not found
  }

  // Other methods will be implemented here 👇
}

• Explanation: This method deletes a node with the specified data from the list.
  • If the list is empty, it returns false.
  • It traverses the list to find the node with the matching data.
  • Depending on the position of the node (head, tail, or middle), it updates the pointers accordingly.
  • The length is decremented, and the method returns true if the node was found and deleted.

Traverse forward

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

  // Previous methods here 👇
  // .
  // .
  // .

  // Traverse forward
  traverseForward() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

  // Other methods will be implemented here 👇
}

• Explanation: This method traverses the list from the head to the tail, printing the data of each node.
  • It starts at the head and continues until it reaches the end of the list (current becomes null).

Traverse backward

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

  // Previous methods here 👇
  // .
  // .
  // .

  // Traverse backward
  traverseBackward() {
    let current = this.tail;
    while (current) {
      console.log(current.data);
      current = current.prev;
    }
  }
}

• Explanation: This method traverses the list from the tail to the head, printing the data of each node.
  • It starts at the tail and continues until it reaches the beginning of the list (current becomes null).

Search for a node

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

  // Previous methods here 👇
  // .
  // .
  // .

  // Search for a node
  search(data) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1; // Node not found
  }

  // Other methods will be implemented here 👇
}

• Explanation: This method searches for a node with the specified data and returns its index.
  • It traverses the list from the head, checking each node's data.
  • If a match is found, it returns the index; otherwise, it returns -1 if the node is not found.

Usage Example

Here's a simple example of how to use our Doubly Linked List:

const list = new DoublyLinkedList();

list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtBeginning(0);
list.insertAtPosition(1.5, 2);

console.log("Forward traversal:");
list.traverseForward();

console.log("Backward traversal:");
list.traverseBackward();

console.log("Search for 2:", list.search(2));

list.deleteNode(1.5);

console.log("After deletion:");
list.traverseForward();

Conclusion

In this article, we've learned about the basics operations of doubly linked lists and how to implement
them in JavaScript. In the next article, we'll be learning about Circular Linked Lists, then we can solve some leetcode problems to deepen our understanding.

Circular Linked Lists Demystified: From Novice to Node Master

Emmanuel Ayinde ・ Oct 6

#javascript #beginners #programming #dsa

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding 👨‍💻🚀