JavaScript: Implement a Doubly Linked List

1. Introduction

A Doubly Linked List (DLL) is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and next node in the sequence) and one data field.

2. Program Overview

In this program, we will implement a doubly linked list. The operations we'll cover include:

1. append() - to insert an element at the end

2. prepend() - to insert an element at the start

3. remove() - to delete a node by its data value

4. display() - to view the list

3. Code Program

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

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

// Function to append a new node at the end
DoublyLinkedList.prototype.append = function(data) {
    let 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;
    }
}

// Function to prepend a new node at the start
DoublyLinkedList.prototype.prepend = function(data) {
    let 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;
    }
}

// Function to remove a node by its data
DoublyLinkedList.prototype.remove = function(data) {
    let currentNode = this.head;
    while (currentNode) {
        if (currentNode.data === data) {
            if (currentNode.prev) currentNode.prev.next = currentNode.next;
            if (currentNode.next) currentNode.next.prev = currentNode.prev;
            if (currentNode === this.head) this.head = currentNode.next;
            if (currentNode === this.tail) this.tail = currentNode.prev;
        }
        currentNode = currentNode.next;
    }
}

// Function to display the list
DoublyLinkedList.prototype.display = function() {
    let currentNode = this.head;
    let result = [];
    while (currentNode) {
        result.push(currentNode.data);
        currentNode = currentNode.next;
    }
    return result.join(' <-> ');
}

// Test the Doubly Linked List
let dll = new DoublyLinkedList();
dll.append(1);
dll.append(2);
dll.append(3);
dll.prepend(0);
console.log("Doubly Linked List: " + dll.display()); // Expected: 0 <-> 1 <-> 2 <-> 3
dll.remove(2);
console.log("After removing 2: " + dll.display());  // Expected: 0 <-> 1 <-> 3

Output:

Doubly Linked List: 0 <-> 1 <-> 2 <-> 3
After removing 2: 0 <-> 1 <-> 3

4. Step By Step Explanation

1. Node Class: Represents each node of our DLL. Every node has data, next (pointer to next node), and prev (pointer to previous node).

2. DoublyLinkedList Class: This is our main DLL class. It starts with head and tail pointers both initialized to null.

3. append(): Adds a node to the end of the list. If the list is empty, the new node becomes the head and tail. Otherwise, we adjust the pointers to add the new node to the end.

4. prepend(): Adds a node to the beginning of the list. If the list is empty, the new node becomes the head and tail. Otherwise, we adjust the pointers to add the new node to the start.

5. remove(): Iterates through the list and removes a node with the specified data. Adjusts pointers accordingly.

6. display(): Iterates through the list and constructs a string representation of the list for easy visualization.

7. The test shows the creation of a DLL, adding nodes, and removing a node.

With the help of the prev and next pointers in each node, navigating and modifying a doubly linked list becomes much easier, especially when compared to a singly linked list.