linkedlist, data structure, algorithms,

Data structure is the organization of data for easy accessibility and processing. There are a good number of them ranging from Array, LinkedList, Stack, Queue, Binary search tree, Graphs, etc and they all have their strengths when it comes to usage. In this article, we will be going through the LinkedList data structure.

This article is intended to be in a series form and we will be going through a singly LinkedList first before looking at doubly LinkedList and some others.

Prerequisites

Understanding Of Javascript
Understanding Of ES2015 Javascript Classes

Let's get Started 😆

via GIPHY

What is a LinkedList?

A LinkedList is a Linear Data Structure that consists of connected nodes, and each node has a value and a pointer reference to the next node in the list. There are two types of LinkedList namely Singly and Doubly LinkedList. The major difference between both LinkedList is that singly LinkedList has its pointer only pointing to the next node in the list while the Doubly LinkedList has its pointer pointing to the previous and next node. It's important to note that LinkedList contains head, tail, and length properties.

Usage

In this article, there will be examples on how to push and pop from a linked list. We will also go through use cases on how to get, shift, unshift, insert and remove a node from linked list. Reversing a linked list is often ask sometimes in technical interviews, we will also see an example of that in this piece.

First of all, we will need to create a class Representation of our Node and LinkedList.

Node Class

class Node

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

LinkedList Class

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

Pushing Into a List

To push an item into a list, we would need to create a new node and then push it into the list. A step by step implementation is as follows:

Declare a push method
The push method should accept a value
Create a new node with the value that was passed into the pushed method
If there is no head in the list, make the new node the head and tail
Otherwise, we would set the next property on the current tail to be the newly created node and also set the newly created node to be the tail.
Then we increment the length of the list and return the list.

 push(val)
    {
       var newNode = new node(val)
       if(!this.head)
       {
           this.head = newNode
           this.tail = this.head
       }
       else
       {
            this.tail.next = newNode
            this.tail = newNode
       }
         this.length++
         return this
    }

    let list = new linkedlist()
    list.push(20)
    list.push(30)
    list.push(40)

Popping From a List

Popping is the process of removing a node from the end of the list. To pop out a node, we would need to traverse through the list till we get to the end. While iterating, we need to keep track of the current and previous nodes. Once we are at the end, we would remove the tail node from the memory and set the next pointer on the previous node to null while setting the previous node before the tail as the new tail.

A step by step is as follows:

Define a pop method
Declare a current variable to hold the starting point of our iteration, which is the head
Declare a previous variable that keeps track of the previous node while the iteration is going on.

It is worth noting that at the beginning, the previous variable is the current variable.

Loop through the list until we reach the tail node
Set the node before the last node as the new tail
Set the next property on the new tail to null
Decrement the length by 1
Return the value removed from the list

Base Case

If the length of the list is empty we should return null
we should check if the length of the list is at 1, then set the head and tail to null since the next node being removed will be the last node.

     pop()
    {

        if(this.length === 0) return undefined

        var current = this.head
        var previous = current

        while(current.next)
        {
            previous = current
            current = current.next
        }

         this.tail = previous
         this.tail.next = null
         this.length --
         if(this.length === 0)
        {
            this.tail = null
            this.head = null
        }
         return current
    }

   let list = new linkedlist()
   list.push(20)
   list.push(30)
   list.push(40)
   list.pop()

In this example, 40 will be returned

Getting From a List

This involves retrieving a node from a particular position in the LinkedList. The method will take in a number representation which is the index of the node to be retrieved from the list, loops through the list till it finds the node at the index that was passed in. Below is the step-by-step implementation of the get method.

Define a get method that takes in an argument
Declare a counter variable
Loop through the list until you reach the index and return the node at that specific index

Base Case

If the index passed is greater or less than zero, return null.

if the index passed is equal to the length of the list, return null.

 get(index)
    {
        if(index < 0 || index > this.length) return null
        var counter = 0
        let current = this.head
        while(counter !== index)
        {
            current = current.next
            counter++
        }
          return current
    }

 let list = new linkedlist()
 list.get(2)

Shifting a List

Shifting is removing a node from the beginning of a LinkedList. With shifting, we remove the current head from the list and then set the next node to the current head as the new head of the list. Imagine you are the side chick of a guy and after all your pressure, he finally displaces the main babe and makes you the main babe, that's exactly how shifting works. Below is the step-by-step flow of shifting.

Define a shift method
Declare a variable to hold the current head
Set the new head property to be the current head’s next property
Decrement the length by 1
Return the value of the node removed or return true

Base Case

If the length of the list is empty we should return null

 shift()
    {
        if(this.length == 0) return null
        var currentHead = this.head
        this.head = currentHead.next
        this.length -- 
        if(this.length === 0)
        {
            this.tail = null
        }
        return currentHead
    }
     let list = new SinglyLinkedList() 
     list.shift()

Unshifting a List

Unshifting involves adding a new node to the beginning of the LinkedList. We have to make the new node the new head and point the current head which is now the previous head to be the next node from the new head. In simple terms, when you were little and got a new toy from your parents, you ignore your current favorite toy for the new toy till you get tired; So in this case, the new toy becomes the head of all the other toys and your current favorite toy becomes the next favorite after the new one. Let us take a look at the step-by-step flow to unshifting a new node.

Define an unshift method that takes a value
Create a new node using the value passed to the function
Declare a variable to store the current head
Set the head property on the list to be that newly created node
Increment the length of the list by 1
Return the LinkedList

Base Case

If there is no head property, set the new node to be the head and tail

  unshift(val)
    {
        let newNode = new node(val)
        if(!this.head)
        {
            this.head = newNode
            this.tail = newNode
        }else
        {
            let currentHeadNode = this.head
            this.head = newNode
            this.head.next = currentHeadNode
            this.length++
            return this
        }

    }
    let list = new SinglyLinkedList() 
     list.unshift(30)

Inserting Into a List

To insert into a LinkedList, we add a new node to a particular position in the list. Below is the step-by-step implementation of the insert method.

Define an insert method that takes in the value and an index argument
We create a new node with the value passed
If the index is equal to the length of the list, we use the push method to add the node
If the index is 0, we use the unshift method to add the new node to the beginning of the list.
If the index is in any other part of the list, we use the get method to access the node previous to the index(index - 1) we want to insert the new node into.
We declare a variable to hold the node at the target index so we can have reference to it.
Set the next value of the node on the previous node to be the new node
Set the next value on the new node to be the node that was previously occupying the index.
Increment the length
Return the LinkedList or true

Base Case

If the position is less than zero or greater than the length, return null

insert(val,index)
    {
        var newNode = new node(val)
        if(index < 0 || index > this.length) return false
     //the double exclamation mark returns the result as true or false
        if(index === 0) return !! this.unshift(val)  
        if(index === this.length)return !! this.push(val)

        var prevNode = this.get(index - 1)
        var temp = prevNode.next
        prevNode.next = newNode
        newNode.next = temp
        this.length++
        return true
    }

  let list = new SinglyLinkedList() 
  list.insert(50,2)

Removing from a List

It involves removing a node from a particular position in the LinkedList. The steps to remove a node are listed below.

Define a remove method that takes an index argument
If the index is the same as the length-1, use the pop method to remove the node
If the index is 0, use the shift to remove the node
We use the get method to locate the node before the target node
We then use the previous node next pointer to get the target node
Use the next pointer on the previous node to chain it with the node after the targeted node
Decrement the LinkedList
Return the target Node or true

Base Case

If the position is less than zero or greater than the length, return null

remove(index)
    {
        if(index < 0 || index > this.length) return false
       //the double exclamation mark returns the result as true or false
        if(index === this.length - 1) return !! this.pop(val)
        if(index === 0) return !! this.shift(val)

        let prevNode = this.get(index - 1)
        let target = prevNode.next
        target.next = null
        let afterTargetNode = target.next
        prevNode.next = afterTargetNode
        this.length--;
        return target;
    }

We have covered the important methods we could implement on LinkedList. I said earlier that we would be implementing a reverse method to overturn the order of a LinkedList.

Let's dive into it!

Reversing a LinkedList

Reversing a LinkedList means changing the order in which the nodes are outputted. The nodes in the list have pointers from the head to the tail and we are going to reverse this order such that the nodes are outputted from tail to head. In other, for us to achieve this, we need to change what the pointer points to[how the pointer works]. Below is the walk-through of the whole process.

Swap the head and tail node, this means the head becomes the tail and vice versa
Declare a previous and next variable. The previous variable will keep track of the node that was currently visited while the next variable will keep track of the node that is next to be visited.
Loop through the List and keep updating the next and previous variable till we get to the end of the list

reverse()
    {

        var current = this.head // holds the current head

        //we do the swap here
        this.head = this.tail 
        this.tail = current

        // since we are have swapped head and tail
        //the new tail will have no previous node so the previous initially is null
        var prev = null 
        var next;

        //we loop through our list, starting from the current, which is the head at the start
        while(current !== null)
        {
            //next variable is pointing to the next node in the list
            //since we initialized our current to be the actual head of the LinkedList,
            // we can have access to the actual next node in the list
            next = current.next 

            //now we set the next node on the current node to be the previous node
            //since we are reversing, the next node from the current head(which is now the tail) would be the 
  previous node
            //e.g at the first iteration
            //30->20->50
            //current = 30
            //current.next = null. Since 30 is now the tail and we are reversing instead of the next to be 20
            //we are reversing the other and the next on 30 becomes null 

            current.next = prev

            //we then set previous to be current node and the current node to be the next node
            prev = current
            current = next

        }
        //return the whole list
           return this

    }
}
var list = new SinglyLinkedList() 
 list.push(30) 
 list.push(20)
 list.push(50)    
 list.push(70) 
 list.reverse()

BIG O Of Some Of The Methods In Singly LinkedList

Insertion O(1): It is easy to insert a new node into a list. Inserting a node takes constant time if we are pushing or unshifting a node into a LinkedList.
Removal O(1) or O(N): Removing a node from the end takes constant time O(N) time. The larger the size of the list, the more time it takes to reach and remove the targeted node. if we are removing a node from the beginning, it takes O(1) constant time since we already keep track of the head, it would be quick to remove the head and point the new head to the next node property in the list.
Searching O(N): Searching for a node means we would need to go through the list before arriving at the node we are looking for and this would take O(N) time depending on the size of the list. The larger the size, the more time it takes to find the node.

Here is the GitHub Link to the implementation of the methods. I would be talking about doubly LinkedList in my next article, feel free to give your feedback and questions on this one.

Teeto

Teeto

Working With LinkedList Data Structure