Understanding Doubly Linked Lists in JavaScript

Photo by Becca Tapert on Unsplash

Doubly linked lists are a efficient data structure widely used in computer science and software development. We will look into the intricacies of doubly linked lists, understand their key components, and explore a practical implementation in JavaScript.

We shall breakdown this example;

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

    display() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// Example usage
const list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.append(30);

list.display();

1. Data: The data or value associated with the node.
2. Pointers: Two pointers, prev and next, which respectively reference the previous and next nodes in the list.

In JavaScript, we can create the Node class to represent these fundamental building blocks:

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

Here, the constructor method initializes a node with its data, setting both prev and next to null initially.

Next, we create the DoublyLinkedList class to manage the list itself. It has two crucial properties:

1. head: Points to the first node in the list.
2. tail: Points to the last node in the list.

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

To populate our doubly linked list, we use the append() method. This method adds a new node to the end of the list:

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

• It creates a new node (newNode) with the provided data.
• If the list is empty (i.e., this.head is null), both head and tail are set to the new node.
• If the list isn’t empty, the new node is connected to the current tail, and the tail is updated to the new node, effectively adding it to the end.

To examine the contents of our doubly linked list, we implement the display() method:

display() {
    let current = this.head;
    while (current) {
        console.log(current.data);
        current = current.next;
    }
}

This method traverses the list from head to tail, printing the data of each node along the way.

const list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.append(30);

list.display();  // Output: 10, 20, 30

Here, we create a DoublyLinkedList instance, add three elements, and display the list's contents.

NOW: having gotten an idea of the example above see if you can understand this below;

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;
        }
    }
    
    delete(data) {
        let currentNode = this.head;
        while (currentNode) {
            if (currentNode.data === data) {
                if (currentNode === this.head) {
                    this.head = currentNode.next;
                    if (this.head) {
                        this.head.prev = null;
                    } else {
                        this.tail = null;
                    }
                } else if (currentNode === this.tail) {
                    this.tail = currentNode.prev;
                    this.tail.next = null;
                } else {
                    currentNode.prev.next = currentNode.next;
                    currentNode.next.prev = currentNode.prev;
                }
                return;
            }
            currentNode = currentNode.next;
        }
    }
    
    display() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// Example usage
const list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);

list.display();  // Output: 5, 10, 20, 30

list.delete(20);
list.display();  // Output: 5, 10, 30t

I hope this article was helpful……