Data Structures & Algorithms in JavaScript(Doubly linked list)

Hello everyone, I'm back from my hibernation, I will continue to post the series about data Structure and algorithms, It's also part of my journey towards learning Data structures and algorithms ... once it for all, As in my engineering yrs, I was struggling to write the simple stack code. Looking back .. I have come a long way But now as a full-time developer. I once again decided to learn ds and algorithms to finish it this time.

Being consistent is the key to success...

Thank you dev community

Now Let's get started with part 6 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover Doubly linked list.

What is the Doubly linked list?

A Doubly Linked List contains an extra pointer, typically called the previous pointer, together with next pointer and data which are there in the singly linked list. - geeksforgeeks.org

List Of Operations Available

• All methods will same as single linked list.We only overwrite the insert, push and removeAt methods.

Implementation of Doubly linked list in Javascript

The doubly linked list is a special type of linked list. We will just extend the linked list class i.e inherit the LinkedList class. we call the parent constructor by super keyword to initialize the count and head properties of the Doubly linked list. besides, it has a tail property which refers to the end of the doubly linked list

class DoubleLinkedList extends LinkedList {
    constructor(func) {
        super(func);
        this.tail = undefined;
    }
}

DoubleLinkedList provides a way of iterating it from start to end or vice versa. We can go forward using next pointer or backward using previous pointer, for this behavior, we will keep track of the previous element in each node, therefore, we will define a DoublyNode Which will extend the Node class, element and next properties will be initialized by parent constructor and a previous property to keep track of the previous element.

class DoublyNode extends Node {
    constructor(element, next, previous) {
        super(element, next);
        this.previous = previous;
    }
}

All methods implementation will be similar to the single linked list. In addition to the next pointer, we also have the previous pointer.

Push

When Pushing an element to a doubly-linked list, we have two scenarios:

• Doubly-linked list is empty.
• Doubly-linked list is not empty and appends element at the end.

First, We will create a DoublyNode passing element as its value if the head is undefined then assign head pointer to the node ({1}) and also tail ({2}). Since the end node points to the tail pointer.

Secondly, If the doubly linked list is not empty we will define a current variable equal to tail ({3}), points the new node to the current.next ({4}) , node.next to current ({5}) and node.next ({6}) to the tail.

   push(element) {
        let node = new DoublyNode(element);
        if (this.head == undefined) {
            this.head = node; //1
            this.tail = node;  //2
        } else {
            let current = this.tail; //3
            current.next = node; //4
            node.previous = current; //5
            this.tail = node; //6

        }
        this.count++;
    }

Insert

To insert an element at a given the position; We validate the index, ie. index the must be greater than zero and less than and equal to count, there are three scenarios,

• Insert an element at the start of the list (Index == 0).
  • We check if the list's head is undefined :
    • If undefined then the same as the push method (head is undefined) ({2}). Set head ({3}) and tail ({4}) to the new Node.
    • Else, move the list's head to the new node.Define current variable equal to head ({1}),Set node.next to current ({6}),current.previous to node ({5}) and head to the new Node ({7}).

• Insert an element at the end of the list (Index == count).
  • This is the same push method. When the list is not empty.

• Insert an element at the middle of the list (Index == n).
  • Adding an element in the middle of the list. First, need to loop through the list until we reach the desired position. In this case, we will loop to index -1, meaning one position before where we desire to insert a new node.
  • When we get out of the loop, the previous variable will be a reference to an element before the index where we would like to insert to new element and the current variable. So first, we link the node's next to current and also current's previous to the node, to change the link between previous and current. we need previous.next to the node and node's previous to the previous.

 insert(element, index) {
        if (index >= 0 && index <= this.count) {

            let node = new DoublyNode(element);
            let current = this.head; //1
            if (index == 0) {
                if (this.head == undefined) { //2
                    this.head = node; //3
                    this.tail = node; //4
                } else {
                    current.previous = node; //5
                    node.next = current;  //6
                    this.head = node;  //7
                }
            } else if (index == this.count) {
                current = this.tail;
                current.next = node;
                node.previous = current;
                this.tail = node;
            } else {
                let previous = this.getElementAt(index - 1);
                current = previous.next;
                previous.next = node;
                node.next = current;
                node.previous = previous;
                current.previous = node;
            }
            this.count++;
        }
    }

RemoveAt

Remove an element at the specified index, we first check if the linked list is empty else return undefined ({1}), After that we valid the index's out of bound error, by check is the index, greater than zero and less than count.there are three scenarios,

• Remove an element at the start of the list

  • Remove a node from the start, we just move the head node to head's next Node, To do that we first, define a current variable equal to head, set the head to the current.next.
  • If the list count is 1 then set the tail to undefined, as end-node points to tail, we need to unset it by setting tail to undefined, else we set head previous to undefined, we need to unlink the previous head node.

• Remove an element at the end of the list

• Remove an element at the middle of the list

   removeAt(index) {
        if (this.isEmpty()) {
            return undefined;
        }
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index == 0) {
                this.head = current.next;
                if (this.count == 1) {
                    this.tail = undefined;
                }else{
                    this.head.previous = undefined;
                }
            }else if (index == this.count-1){
                current = this.tail;
                this.tail = current.previous;
                this.tail.next = undefined;
            }else{
                current = this.getElementAt(index);
                const previous = current.previous;
                // link previous with current's next
                previous.next = current.next;
                current.next.previous = previous;
            }
            this.count --;
            return current.element;
        }
    }

Get the full source code here

Difference between Single Listed List and Doubly Listed List

Single Listed List	Doubly Listed List
Uses Less Memory	Takes 2x Memory
Simple Implementation	fairly hard Implementation
Cannot easily access the previous element	Can easily access the previous element using the previous property

Conclusion :

Methods	Complexity
insert at head	O(1)
insert at tail	O(1)
search an element	O(n)
remove head element	O(1)
remove any element(removeAt)	O(n)

So, stay tuned for the next blog, in which I will cover another DS Circular Linked List.