Follow by Email

Data Structures & Algorithms in JavaScript(Doubly linked list)

Hello Everyone, this is 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

Doubly Linked List

List Of Operations Available

  • All methods will same as single linked list.We only override the insertpush 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 classelement 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 start of the list

  • 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 end of the list

  • 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 an element at the middle of the list


    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 start of the list

  • Remove an element at the end of the list

Remove an element at the end of the list

  • Remove an element at the middle 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;
        }
    }

you get the full source here

Difference between Single Listed List and Doubly Listed List

       Single Listed ListDoubly Listed List
       Uses Less MemoryTakes 2x Memory
Simple Implementationfairly hard Implementation
Cannot easily access the previous elementCan easily access the previous element
 using the previous property

Conclusion :

MethodsComplexity
insert at headO(1)
insert at tailO(1)
search an elementO(n)
remove head elementO(1)
remove any element(removeAt)O(n)

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

Data Structures & Algorithms in JavaScript(Doubly linked list) Data Structures & Algorithms in JavaScript(Doubly linked list) Reviewed by RS Coder on May 14, 2020 Rating: 5

No comments:

Disqus Shortname

banner image
Powered by Blogger.