Javascript Data Structure - Doubly Linked list

Definition

Doubly linked list is a type of linked list in which each node apart from storing its data has two pointers. The first pointer points to the previous node in the list and the second pointer points to the next node in the list. The head node its previous value points to NULL and similar to the tail node its next value points to null.

and saving a second reference to nodes requires more space in memory.

let's recap the main properties of the linked list:

The main properties of the linked list are:

length: The number of nodes in the linked list
Head: The first node
Tail: The last node

See more in my last post Javascript Data structure - Linked list

in this case the nodes will be contain the next properties:

next: pointer to the next node
value: actual value of the node
prev: pointer to the previous node

and the main operations here are:

append: Add a node to the end in the linked list
prepend: Add a node to the beggining the linked list
removeFirst: remove the first node (head)
removeLast: remove the last node(tail)
search: find a node by his value and returned
remove: remove a node by its value from the linked list

Implemetation

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    //** add at the end of the linked list */
    append(value) {
        // if empty
        if (!this.tail) {
            this.tail = { value };
            this.head = this.tail;
        } else {
            let oldTail = this.tail;
            this.tail = { value };
            oldTail.next = this.tail;
            this.tail.prev = oldTail;
        }
        this.length++;
    }

    //** add to the beggining  */
    prepend(value) {
        if (!this.head) {
            this.tail = { value };
            this.head = this.tail;
        } else {
            let oldHead = this.head;
            this.head = { value };
            oldHead.prev = this.head;
            this.head.next = oldHead;
        }
        this.length++;
    }
    removeFirst() {
        if (!this.head) {
            throw new Error("The list is empty");
        } else {
            let tempHead = this.head;
            // ** when theres only one node
            if (this.head === this.tail) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = this.head.next;
                this.head.prev = null;
            }
            this.length--;
            return tempHead.value;
        }
    }
    removeLast() {
        if (!this.tail) {
            return null;
        } else {
            let tempTail = this.tail;
            if (this.tail === this.head) {
                this.tail = null;
                this.head = null;
                this.length--;
            } else {
                this.tail = this.tail.prev;
                this.tail.next = null;
                this.length--;
                return tempTail.value;
            }
        }
    }
    search(value) {
        let currentNode = this.head;
        while (currentNode) {
            if (currentNode.value === value) {
                return currentNode;
            }
            currentNode = currentNode.next;
        }
        return null;
    }
    remove(value) {
        let tempNode = this.search(value);

        if (tempNode === this.tail) {
            this.removeLast();
            return;
        } else if (tempNode === this.head) {
            this.removeFirst();
            return;
        } else {
            tempNode.prev.next = tempNode.next;
            tempNode.next.prev = tempNode.prev;
        }
        this.length--;
    }
}

Create a class with a constructor that initializes the head, tail and length of the linked list.
Define a method search() that iterate through the list to find a specific node.
Define two convenience methods, append() and prepend() that use to insert a new element at the start or end of the nodes respectively and increase the length.

Define a method remove() that uses the search to find the node and replacing its value to delete it.

Define two convenients methods removeFirst() and removeLast() to remove the head or the tail.

let list = new LinkedList();

list.append(1);
list.append(2);
list.append(23);
list.append(3);
list.prepend(55);
list.append(2);
list.append(22);

list.remove(22);

console.log(list);

In my last post of linked list I made a mistake writting the linked list, the point of the linked list is to avoid arrays, so in this post I want to make up for my mistake :) this series is for learning and thank u all for the feedbacks.

Blog

Javascript Data Structure - Doubly Linked list

Rivier Grullon

Definition

Implemetation

Join Our Newsletter. No Spam, Only the good stuff.

Related