Hey ! I think it’s time to look at another type of Linked-list structure called Doubly linked-list. remember we said singly link list is a linear data structure that has a node containing a Value(Data) and the next pointer that keeps track on the next node it’s connected to. in the other hand Doubly linked list isn’t so different from singly linked-list except that in a doubly linked-list not only it has a next slot to connect to the next node but also has a previous slot(memory) to link back to the previous one so it means just adding a previous to the construction of the node makes it a doubly linked list. Let’s implement our Doubly Linked-list first Node.

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

Nothing really special at this stage but what of if you want to step up things a bit to create a push() method on this doubly Linked-List what is it going to be ? definitely not like the previous singly type but will look almost the same in the exception of the new introduction of the previous. let’s take a look at how a push() method is defined on a doubly linked-list.

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

class DoublyLinkedList {
 constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(this.length === 0){
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
        return this;
    } 
}

Here we create a new node with the value that is going to be supplied to it Node(val) now we check if there is nothing in the head which means the head is ready to take a new node or else we shift the current info into the next node memory before attempting the assignment of the new node. but notice in this edge case we used this.length instead of this.head == null or (!this.head). They are all the same thing since we are just checking to confirm if the first head is empty or not. proceeding from there like I mentioned earlier if the length of the list is 0 or the head is null then give the new node to the head and the tail altogether or else trace the tail.next and assign the new node to it instead and because previous is now in the equation we create a new memory at the back of the new node to be the previous and assign the tail to it temporally which will become the new node eventually in the long run. continue doing the same thing each time a push method is evoked and return the whole list at the end.

the above is responsible for the push() method and you can test it by just defining a new node variable and push a value into it anytime. see below example.

var list = new DoublyLinkedList()
list.push("Harry")

the following will be the other subsequent methods we created for the singly linked-list but this time round with some more tweaks because we’re dealing with another type structure. take a look and make some meaning out of it.

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

class DoublyLinkedList {
  constructor(){
   this.head = null;
   this.tail = null;
   this.length = 0;
 }
 push(val){
    var newNode = new Node(val);
    if(this.length === 0){
      this.head = newNode;
      this.tail = newNode;
    } else {
       this.tail.next = newNode;
       newNode.prev = this.tail;
       this.tail = newNode;
    }
     this.length++;
     return this;
 } 
 pop(){
   if(!this.head) return undefined;
     var poppedNode = this.tail;
      if(this.length === 1){
        this.head = null;
        this.tail = null;
      } else {
        this.tail = poppedNode.prev;
        this.tail.next = null;
        poppedNode.prev = null;
      }
        this.length--;
        return poppedNode;
    }
  shift(){
   if(this.length === 0) return undefined;
     var oldHead = this.head;
      if(this.length === 1){
        this.head = null;
        this.tail = null;
      }else{
        this.head = oldHead.next;
        this.head.prev = null;
        oldHead.next = null;
     }
    this.length--;
    return oldHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

var list = new DoublyLinkedList()
list.push("Hello")
list.push("World")
list.push("I here to help")

I understand perfectly this can be intimidating and overwhelming for the first time even the second and the third time but I promise you if you clear your head and tackle it that number of times it will definitely click in your head on the nth attempt and that’s it the magic begins for you.

Now let’s take a look at the Big O complexities of our doubly Linked-List

Searching will always results in O(n) Linear because of the iteration it has to go through when looking for records.

Accessing will also not make any difference from the searching so will remain in O(n) Linear

Insertion however makes a difference in the best case scenarios with O(1) Constant but will become difficult in cases where it has to be done somewhere from the middle of the list

Deletion at the beginning and the end will also be faster with O(1) Constant but will go down the same road as Insertion in the worse case scenario O(n) Linear.

There is a definite trade offs in Space Complexity when it comes to doubly linked list, it’s a O(n) Linear space complexity because it has an extra memory to create as the Previous slot making the space much bigger as the data grows and more nodes has to be added.

Okay I think we can rest for today and come to the arena next time. Stay safe 🙂