JavaScript Program to Implement a Doubly Linked List

Introduction

A Doubly Linked List is a linear data structure where each node has a reference to both the next and previous node. This allows traversal in both directions, forward and backward, compared to a singly linked list where traversal is only possible in one direction. Each node in a doubly linked list contains:

• Data: The value stored in the node.
• Next Pointer: A reference to the next node in the list.
• Previous Pointer: A reference to the previous node in the list.

This guide will walk you through writing a JavaScript program to implement a doubly linked list with basic operations such as insertion, deletion, and traversal.

Problem Statement

Create a JavaScript program that:

• Implements a Doubly Linked List.
• Supports operations such as:
  • Insertion: Insert a node at the head, tail, or at a specific position.
  • Deletion: Remove a node from the head, tail, or at a specific position.
  • Traversal: Traverse the list forward and backward to display the elements.

Example:

• Input: Insert values 10, 20, 30, 40
• Output (forward): 10 <-> 20 <-> 30 <-> 40

Solution Steps

1. Define a Node Class: Create a class that stores the data, the next node, and the previous node.
2. Define the Doubly Linked List Class: Implement methods for:
   • Insertion at the head, tail, or specific position.
   • Deletion from the head, tail, or specific position.
   • Traversal in both directions.
3. Display the List: Traverse the list and print the nodes.

JavaScript Program

Step 1: Define the Node Class

// JavaScript Program to Implement a Doubly Linked List
// Author: https://www.rameshfadatare.com/

class Node {
    constructor(data) {
        this.data = data;       // Data part of the node
        this.next = null;       // Pointer to the next node
        this.prev = null;       // Pointer to the previous node
    }
}

Step 2: Define the Doubly Linked List Class

class DoublyLinkedList {
    constructor() {
        this.head = null;  // Head of the list
        this.tail = null;  // Tail of the list
    }

    // Insert at the end (tail) of the doubly linked list
    insertAtEnd(data) {
        const newNode = new Node(data);

        if (this.head === null) {
            // If the list is empty, set both head and tail to the new node
            this.head = this.tail = newNode;
        } else {
            // Otherwise, append the new node at the end and update the tail
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }

        console.log(`${data} inserted at the end`);
    }

    // Insert at the beginning (head) of the doubly linked list
    insertAtBeginning(data) {
        const newNode = new Node(data);

        if (this.head === null) {
            // If the list is empty, set both head and tail to the new node
            this.head = this.tail = newNode;
        } else {
            // Insert the new node before the current head
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }

        console.log(`${data} inserted at the beginning`);
    }

    // Delete a node from the end of the list
    deleteFromEnd() {
        if (this.tail === null) {
            console.log("List is empty");
            return;
        }

        console.log(`${this.tail.data} deleted from the end`);

        if (this.head === this.tail) {
            // If there's only one element, set both head and tail to null
            this.head = this.tail = null;
        } else {
            // Update the tail to the previous node
            this.tail = this.tail.prev;
            this.tail.next = null;
        }
    }

    // Delete a node from the beginning of the list
    deleteFromBeginning() {
        if (this.head === null) {
            console.log("List is empty");
            return;
        }

        console.log(`${this.head.data} deleted from the beginning`);

        if (this.head === this.tail) {
            // If there's only one element, set both head and tail to null
            this.head = this.tail = null;
        } else {
            // Update the head to the next node
            this.head = this.head.next;
            this.head.prev = null;
        }
    }

    // Traverse the list forward (from head to tail)
    traverseForward() {
        if (this.head === null) {
            console.log("List is empty");
            return;
        }

        let current = this.head;
        let result = "";

        console.log("List (Forward):");
        while (current !== null) {
            result += current.data + (current.next ? " <-> " : "");
            current = current.next;
        }

        console.log(result);
    }

    // Traverse the list backward (from tail to head)
    traverseBackward() {
        if (this.tail === null) {
            console.log("List is empty");
            return;
        }

        let current = this.tail;
        let result = "";

        console.log("List (Backward):");
        while (current !== null) {
            result += current.data + (current.prev ? " <-> " : "");
            current = current.prev;
        }

        console.log(result);
    }
}

Step 3: Example Usage

// Example usage of the Doubly Linked List
const dll = new DoublyLinkedList();

// Insertion at the end
dll.insertAtEnd(10);
dll.insertAtEnd(20);
dll.insertAtEnd(30);
dll.insertAtEnd(40);

// Traverse forward
dll.traverseForward(); // Output: 10 <-> 20 <-> 30 <-> 40

// Insertion at the beginning
dll.insertAtBeginning(5);

// Traverse forward and backward
dll.traverseForward();  // Output: 5 <-> 10 <-> 20 <-> 30 <-> 40
dll.traverseBackward(); // Output: 40 <-> 30 <-> 20 <-> 10 <-> 5

// Deletion from the beginning and end
dll.deleteFromBeginning(); // Output: 5 deleted from the beginning
dll.deleteFromEnd();       // Output: 40 deleted from the end

// Traverse forward again
dll.traverseForward();     // Output: 10 <-> 20 <-> 30

Output Example

10 inserted at the end
20 inserted at the end
30 inserted at the end
40 inserted at the end
List (Forward):
10 <-> 20 <-> 30 <-> 40
5 inserted at the beginning
List (Forward):
5 <-> 10 <-> 20 <-> 30 <-> 40
List (Backward):
40 <-> 30 <-> 20 <-> 10 <-> 5
5 deleted from the beginning
40 deleted from the end
List (Forward):
10 <-> 20 <-> 30

Explanation

Step 1: Define the Node Class

• The Node class represents each node in the doubly linked list. Each node has:
  • data: The value stored in the node.
  • next: A reference to the next node in the list.
  • prev: A reference to the previous node in the list.

Step 2: Define the Doubly Linked List Class

• Insert at End: The insertAtEnd() method inserts a node at the tail of the list.
• Insert at Beginning: The insertAtBeginning() method inserts a node at the head of the list.
• Delete from End: The deleteFromEnd() method removes the node from the tail of the list.
• Delete from Beginning: The deleteFromBeginning() method removes the node from the head of the list.
• Traverse Forward: The traverseForward() method traverses the list from the head to the tail and prints the nodes.
• Traverse Backward: The traverseBackward() method traverses the list from the tail to the head and prints the nodes.

Step 3: Example Usage

• The doubly linked list is created, and various operations such as insertion, deletion, and traversal are performed.

Conclusion

This JavaScript program implements a doubly linked list with basic operations like insertion, deletion, and traversal. Doubly linked lists are useful when you need to efficiently traverse or modify a list in both directions, making them a versatile data structure for various applications.