Hey, So in our last post we spoke about Data Structures and leant how a class is created. Today! it’s time to get started with one of the Data Structures called Linked List for that matter Singly Linked-list. A Linked list is just like an array with a difference, remember we said arrays are linear collections of data that are backed by their indexes which hold them in place ? well Linked-List is also a Linear Data Structure but this time not bound by any indexes but rather are linked to each other through their Next memories. So basically a linked-list is a collection of Nodes which are made up of Values and their Next Links.  ie. Node=Value & Next. in the last section we had a look at how to create JavaScript classes for our data structures, so let’s represent a Node in a class constructor

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

By observing our class we provided a val to the constructor as the value that will go into our very first node, the next link will be null in this case because this is just the beginning of the list with the first node so it doesn’t point to anything, therefore remaining null for now. we then continue with our main purpose which is the Linked-List and we will start with a Singly Linked-List. 

A Singly Linked-List by definition and design will be the one that contains a Head, a Tail and the Length. These three elements in twist are going to determine where a node is situated at a time and how other methods can be derived from their movements. let’s take a look at a Singly Linked-List in action.

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

This should be our SinglyLinkedList Template which we will use to build any kind of list in this category including the various methods/Functions that can be performed on it. At this stage it is possible to call our first LinkedList but it won’t mean anything because there is no data to be or value to manipulate of feed into the list. but here is how we call a list.

var list = new SinglyLinkedList();
console.log(list);

Guess What our result is going to be in this case SinglyLinkedList {head: null, tail: null}. there you have it null because nothing has been done yet.

Now Our first method here will be a push() Function/Method to enable us add a node to our list. putting everything together now with the push method we should have the following.

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

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

  push(val) {
    const NEW_NODE = new Node(val);
    if (!this.head) {
      this.head = NEW_NODE;
      this.tail = this.head;
    } else {
      this.tail.next = NEW_NODE;
      this.tail = NEW_NODE;
    }
    this.length++;
    return this;
  }

}

var list = new SinglyLinkedList();
list.push(85);
//list.push(100);
console.log(list);

We’ve done nothing special, we just created a method to add a value (Node) to the list and this is how it works.

we create a new node that contains our value to be pushed, so for an empty list we check the head exists if not we then place the Head to be the holder of out value. So what about our tail ? well since the head was empty and we pushed a value to it as the saying goes “To whom much is given much ie required” so since the tail also need be present at all cost then it gives its state to the tail which in this case becomes the head. If not it means the head it already occupied so therefore the next pointer of the tail becomes the new node created. I know this is a bit conceptual but you can think of it as any 4 legged animal heading to your left sight followed by another with their tails in the mouth of the preceding one, you keep on adding more and more anytime you need to add a new one(Node)

There are couple of Methods that can be run on this Linked-List ie.

pop() For removing the Last Node from the list

shift() For removing the first Node from the list

unshift() For adding one or more Nodes at the beginning

get() For getting a particular index value of a given node

set() For creating and storing a preferred value at a particular place in the list

insert() Similar to set() but this one removes the current index value before storing into the memory

remove() Removes a particular indexed Node from the node.

The indexes mentioned here are not that of the arrays but derived from the length of the List.

let’s take a look at how those constructions are made in JavaScript.

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

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

  push(val) {
    const NEW_NODE = new Node(val);
    if (!this.head) {
      this.head = NEW_NODE;
      this.tail = this.head;
    } else {
      this.tail.next = NEW_NODE;
      this.tail = NEW_NODE;
    }
    this.length++;
    return this;
  }

    pop() {
    if (!this.head) return undefined;
    while (this.head.next) {
      this.head = this.head;
      this.head = this.head.next;
    }
    this.tail = this.head;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return this.head;
  }

   shift() {
    if (!this.head) return undefined;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    return this.head;
  }
  unshift(val) {
    let NEW_NODE = new Node(val);
    if (!this.head) {
      this.head = NEW_NODE;
      this.tail = this.head;
    }
    NEW_NODE.next = this.head;
    this.head = NEW_NODE;
    this.length++;
    return this;
  }

  get(index) {
    if (index < 0 || index >= this.length) return null;
    let counter = 0;
    while (counter !== index) {
      this.head = this.head.next;
      counter++;
    }
    return this.head;
  }
  set(index, val) {
    if (this.get(index)) {
      this.get(index).val = val;
      return true;
    }
    return false;
  }
  insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return !!this.push(val);
    if (index === 0) return !!this.unshift(val);

    let NEW_NODE = new Node(val);
    let prev = this.get(index - 1);
    let temp = prev.next;
    prev.next = NEW_NODE;
    NEW_NODE.next = temp;
    this.length++;
    return true;
  }
  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    let prev = this.get(index - 1);
    prev.next = prev.next.next;
    this.length--;
    return prev.next;
  }
}

var list = new SinglyLinkedList();
list.push(85);
list.push(100);
list.pop();
list.shift();
list.unshift(85);
list.set(3, 45);
list.insert(2, 65)
list.remove(1)
console.log(list);

you can take them one after the other to see how they are really working to get to their final meaning.

Searching & Accessing on linked list have a worse and average case scenario of O(n) Linear time complexity by standard because at least an iteration is going to be done looking from the very Head of the list to get to the desired result.

Insertion on the other hand is very fast and handy because it does not require any adjustment rather it determines the index on which the operation is to be done and forwards the value into that memory. therefor has O(1) Constant time complexity.

Deletion similarly behaves like the insertion procedure but this time takes a node of the list. also it has O(1) Constant time complexity but not to say this is definitely in the case of a Singly Linked-List, under different circumstance it goes up to becoming O(n) Linear.

Singly Linked-List can be a little consuming and demanding so the best way to understand it to take it bit by bit until you grasp the whole concept. Until next time keep the fire burning 🙂