Double linked list in javascript

A linked list is a data structure which contains a value and reference to its nearest other value.

There are two types of linked list -

1. Single linkedlist - Single linked list contains value & reference to its next child. ,Please read this article for more on single linked list -https://ujjwalkrgupta.medium.com/linked-list-in-javascript-1900d8365430
2. Double linkedlist - Double linked list contains value & reference to both previous and next child.

let’s write program to add a value to double linked list -

class Node {
    constructor(value) {
        this.data = value;
        this.next = null;
        this.prev = null;
    }
}
class DoubleLinkedList {
    constructor() {
        this.root = null;
    }
    add(value) {
        const node = new Node(value);
        let pointer = this.root;
        if (pointer == null) {
            this.root = node;
        } 
        else {
            while (pointer.next != null) {
                pointer = pointer.next;
            }
            node.prev = pointer;
            pointer.next = node;
        }
    }
}
const list = new DoubleLinkedList();
list.add(2);
list.add(4);
list.add(6);
console.log(list)

So we will find a node until next is null and add node to it, make node prev value as pointer.

Since double linked list can be visited both ways i.e previous and next. It becomes very easy to delete a node.

Delete Node

we will have to find the node by traversing and use its prev and next ref to connect other nodes.

So in layman terms -

prev = node.prev
next = node.next
prev.next = next;
next.prev = prev;  

now node is removed as no one contains information about this.

Let’s write the program to delete node -

class Node {
    constructor(value) {
        this.data = value;
        this.next = null;
        this.prev = null;
    }
}
class DoubleLinkedList {
    constructor() {
        this.root = null;
    }
    add(value) {
        const node = new Node(value);
        let pointer = this.root;
        if (pointer == null) {
            this.root = node;
        } else {
            while (pointer.next != null) {
                pointer = pointer.next;
            }
            node.prev = pointer;
            pointer.next = node;
        }
    }
   delete(value) {
        if (this.root.data === value) {
            this.root = this.root.next;
        } else {
            let pointer = this.root;
            while (pointer.next != null) {
                if (pointer.data === value) {
                    const prev = pointer.prev;
                    const next = pointer.next;
                    prev.next = next;
                    next.prev = prev;
                    return;
                }
                pointer = pointer.next;
            }
        }
    }
}
const list = new DoubleLinkedList();
list.add(2);
list.add(4);
list.add(6);
list.delete(4);
console.log(list)