Doubly Linked List Data Structure

Doubly linked lists are a fundamental data structure in computer science, offering advantages over singly linked lists in certain scenarios. This post will look at the concept of doubly linked lists in JavaScript, explaining their functionality, benefits, and providing practical code examples.

What is a Doubly Linked List?

A doubly linked list is a linear collection of data elements, called nodes, where each node points to both its previous and its next node in the sequence. Unlike a singly linked list, which only allows traversal in one direction, a doubly linked list enables bidirectional traversal, enhancing flexibility and efficiency in certain operations. Each node typically contains three properties:

• data: The value stored in the node.
• prev: A pointer to the previous node in the list.
• next: A pointer to the next node in the list.

The first node is known as the head, and the last node is known as the tail.

Advantages of Doubly Linked Lists

• Bidirectional Traversal: The most significant advantage. You can easily traverse the list in both forward and backward directions.
• Efficient Insertion and Deletion: Inserting or deleting a node only requires modifying a few pointers, making these operations relatively fast, especially when compared to arrays. This is because you don’t need to shift elements.
• Easy Access to Previous Node: This allows for quick access to the preceding element, which simplifies certain algorithms.

Disadvantages of Doubly Linked Lists

• Increased Memory Overhead: Each node requires an extra pointer (prev) compared to a singly linked list, resulting in higher memory consumption.
• Slightly More Complex Implementation: The added complexity of managing two pointers can make the code slightly more involved.

Implementing a Doubly Linked List in JavaScript

Let’s create a simple implementation of a doubly linked list in JavaScript:

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

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

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

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

  printList() {
    let current = this.head;
    let str = "";
    while (current) {
      str += current.data + " <-> ";
      current = current.next;
    }
    console.log(str.slice(0, -5)); // Remove trailing "<-> "
  }
}

// Example Usage
const list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.prepend(5);
list.append(30);
list.printList(); // Output: 5 <-> 10 <-> 20 <-> 30

This code provides basic functionality for appending and prepending nodes. You can extend this class to include methods for insertion at specific positions, deletion, searching, and other operations.