Working with Doubly Linked Lists in JavaScript

Are you familiar with the concept of linked lists? Have you ever wondered how to efficiently insert, delete, or search for elements in a list? If so, then doubly linked lists might be the solution you’re looking for. In this article, we’ll dive into the world of doubly linked lists in JavaScript and explore their implementation, operations, and use cases.

What is a Doubly Linked List?

A doubly linked list is a data structure consisting of a sequence of elements, connected through links, where each element contains a reference to both the previous and the next element. This bidirectional linking allows for efficient traversal in both directions. Each element in the list is represented by a node, which contains the data and the references to its previous and next nodes.

Here’s an example of how a doubly linked list looks:

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

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

Operations on Doubly Linked Lists

Doubly linked lists offer various operations that enable efficient manipulation and traversal of the list. Let’s explore a few important operations:

1. Insertion

To insert a new element, we need to create a new node and adjust the necessary links. Here’s an example of how to insert an element at the beginning of a doubly linked list:

// Insert at the beginning
insertAtBeginning(data) {
  const newNode = new Node(data);

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

2. Deletion

Deleting an element involves adjusting the links to bypass the node we want to remove. Here’s an example of how to delete an element from a doubly linked list:

// Delete by value
deleteByValue(data) {
  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;
      }
      break;
    }
    current = current.next;
  }
}

3. Traversal

Traversing a doubly linked list can be done in both directions: from the head to the tail and from the tail to the head. Here’s an example of how to traverse the list and print its elements:

// Traverse from head to tail
traverseForward() {
  let current = this.head;

  while (current) {
    console.log(current.data);
    current = current.next;
  }
}

// Traverse from tail to head
traverseBackward() {
  let current = this.tail;

  while (current) {
    console.log(current.data);
    current = current.prev;
  }
}

Use Cases for Doubly Linked Lists

Doubly linked lists are versatile data structures and find applications in various scenarios. Some common use cases include:

• Implementation of caches or recently used lists, where elements can be easily moved to the front or back.
• Undo/redo functionality in text editors, where the previous and next states can be accessed quickly.
• Navigation systems in web browsers, where the forward and backward actions are important.

Conclusion

Doubly linked lists are powerful data structures that allow efficient manipulation and traversal of elements. They offer bidirectional linking and are suitable for scenarios requiring efficient insertion and deletion. By understanding the implementation and operations of doubly linked lists in JavaScript, you can leverage their benefits in your own projects.

So, the next time you find yourself needing a data structure with easy traversal in both directions, consider using a doubly linked list in JavaScript.

Happy coding!