Singly Linked Lists Implementation in JavaScript and Python

What is a Linked List?

A linked list according to codementor is a data structure that can store an indefinite amount of items. These items are connected using pointers in a sequential manner. The elements of a linked list are called the nodes. A node has two fields i.e. data and next. The data field contains the data being stored in that specific node. It cannot just be a single variable. There may be many variables presenting the data section of a node. The next field contains the address of the next node. So this is the place where the link between nodes is established. I will use the abbrev SLL to refer to a linked list.

My definition is simple, it is a data structure that consists of nodes with a value property for storing data and the next property pointing to the next node. In this way, a node only knows about its next node and not about the rest of the nodes in the chain.

Operations we to be Implemented

• push //add node a the end
• pop // remove node at the end
• shift // remove node at the beginning
• unshift // add a node at the beginning
• get // get node at a specific index or according to criteria
• set // change node value attribute
• insert //
• remove
• reverse // reverse the direction of the list

NB: Below I have done a deep dive into each function or method implementation. All the functions or methods are inside the class: Skip to the end to see the full code implementation then comeback and follow-through

Let's begin, ps: I will be doing the implementations in both Javascript and Python.

Push

In the push function, you will always be adding a node at the end of the list. The steps to follow are outlined below.

Step 1 - Create a newNode with given value and newNode → next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode.
Step 4 - If it is Not Empty then point the tails next attribute to the newNode
Step 5 - then reset the tail to point to the newNode and increment the size

code implementation in JavaScript:

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

    }
}

class SLL{
    constructor(){
        this.head= null
        this.tail= null
        this.size= 0

    }

    push(val){
        let newNode= new Node(val);
        if(!this.head){
            this.head=newNode
            this.tail= newNode
            this.size++
            return this
        }
        this.tail.next = newNode
        this.tail = newNode
        this.size++
        return this
    }
}

let list =new SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)

In python:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


class SLL:
    def __init__(self):
        self.head=None
        self.tail= None
        self.size=0

    def traverse_list(self):
        if(self.head is None):
            print("No elements in this list")
            return
        else:
            n = self.head
            while n is not None:
                print(n.val)
                n = n.next


    def push(self,val):
        newNode =  Node(val)

        if(self.head == None):
            self.head = newNode
            self.tail = newNode
            self.size+=1
            return self
        self.tail.next= newNode
        self.tail = newNode
        self.size+=1
        return self
list = SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
list.traverse_list()

Pop

In the pop function, this involves always removing from the end. The steps to follow are as below

step 1 - Handle the edge case if the list is empty return None or undefined
step 2 - Create a current and newTail variable, set the current variable to the head node then set the newTail to the current variable
step 3 - traverse the list while current.next exists and setting newTail equal to the current node after each iteration.
The loop will break at the n-1 node if we assume the size of the nodes is n
step 4 - Set the tail attribute equal to the new tail. the tail .next equal to null and decrement the size of the list by 1.
step 5 - check if the size is zero, if so set the head and tail equal to None or null then return the removed node or list

Code implementation in Javascript :

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

In python:

def pop(self):
        if self.head ==None:return
        current = self.head
        new_tail = None
        while current.next is not None:
            new_tail = current
            current = current.next

        self.tail = new_tail
        self.tail.next = None
        self.size-=1
        if self.size == 0:
            self.head = None
            self.tail = None
        return self

Shift

This involves removing the first node in the list.
The steps to follow are below:

step 1: Check if the head exists otherwise return early
step 2: Initiate a variable called temp set it equal to the head property
step 3: set the head property to be the current heads next property
step 4: decrement the size by 1
step 5: Edge case check if the size is down to zero if it is set the tail to null and return the list

Code implementation in Javascript :

shift(){
       if(!this.head) return undefined
       let temp = this.head
       this.head = this.head.next
       this.size --
       if(this.size ===0){
           this.tail =null
       }
       return temp
   }

In python:

def shift(self):
        if self.head == None: return 
        temp = self.head
        self.head = self.head.next
        self.size-=1
        if(self.size == 0):
            self.tail = None
        return temp

Unshift

From the name unshift you can guess it is the opposite of shift and it involves adding a node a the beginning. Follow the steps below:

step 1: Create a variable newNode and instantiate the Node class will the val passed in.
step 2: If there is no head property set the head property and tail property equal to the newNode
step 3: if there is a head property set the newNodes's next property to the head property and then set the head property to the newNode
step 4: Increment the size by 1 and return the list

Code implementation in Javascript :

 unshift(val){
       let newNode = new Node(val);
       if(!this.head){
           this.head= newNode;
           this.tail = newNode;
       }else{
           newNode.next = this.head
           this.head = newNode
       }
       this.size++
       return this


   }

In python:

def unshift(self,val):
        newNode = Node(val)
        if self.head == None:
            self.head = newNode
            self.tail = newNode
        else:
            newNode.next = self.head
            self.head = newNode
        self.size+=1
        return self

Get

Get method is just is a search criterion for a node it can use an index or value of the node but in this case, I will just use the index. Follow the steps outline below:

step 1: If the index is less than 0 or greater than or equal to the size property return early
step 2 Create variable count set to zero , create variable current set it equal to the head property
step 3: count is not equal to index set current=current.next and increment count by 1
step 4: when the loop breaks return current

Code implementation in Javascript :

  get(index){
       if(index<0 || index >= this.size)return undefined;
       let count=0;
       let current= this.head;
       while(count !== index){
           current= current.next;
           count++
       }
       return current;


   }

In python:

def get(self,index):
        if index <0 or index >=self.size:return
        current= self.head
        count = 0
        while count != index:
            current = current.next
            count+=1
        return current

set

This method will use the Get method to find the node we want and set its value attribute to something else. Follow the steps outlined below:

step 1 : Create a node variable set it to the function get with index passed in as a parameter
step 2 : If the node variable is set to a Non-null or Non- None value set the val property of the node to the new val then return true otherwise return false

Code implementation in Javascript :

  set(index, val){
        let node = this.get(index);
        if(node){
            node.val = val;
            return true;
        }
        return false;
   }

In python:

def set(self,index,val):
        node = self.get(index)
        if node :
            node.val = val
            return True
        return False

Insert

This method will insert a node at a specific point, it will also use the Get method as a helper method to determine where to insert the node. Follow the steps below:

Step 1: If the index parameter is less than zero or greater than the size property return early
step 2: if the index parameter is equal to zero, the return the unshift method with the val parameter passed in
step 3: if the index is equal to the size property return the push method with the val parameter passed in
step 4: Create a variable newNode and instantiate the Node class will the val passed in.
step 5: Get the node at the index -1 position
step 6: Create a temp variable and set it equal to the current node's next property
step 7: set the current node's next property to the newNode and newNodes's next property to temp.
step 8: Increment the size property by 1 and return the list

Code implementation in Javascript :

insert(index, val){
       if(index<0 || index > this.size ) return undefined
       if(index === 0){
           this.unshift(val);
       }else if(index === this.size){
           this.push(val);
       }else{
           let newNode = new Node(val);
           let node  = this.get(index-1);
           let temp = node.next;
               node.next = newNode;
               newNode.next = temp;
       }

      this.size++;
      return this;

   }

In python:

def insert(self,index, val):
        if index<0 or index> self.size: return
        if index == 0: return self.unshift(val)
        if index == self.size: return self.push(val)
        newNode = Node(val)
        prevNode = self.get(index-1)
        temp = prevNode.next
        prevNode.next = newNode
        newNode.next = temp
        self.size+=1
        return self

Remove

This method removes an element from the list.The steps to follow are outlined below:

Step 1: If the index parameter is less than zero or greater than or equal to the size property return early
step 2: if the index parameter is equal to zero, the return the shift shift method.
step 3: if the index is equal to the size property minus
1 return the pop method.
step 4: Create a variable prevNode and set it to the results of get method with index-1.
step 5: Get the node at the index -1 position
step 6: Create a temp variable and set it equal to the prevNode's next property
step 7: set the prevNode's next property to the temp's variable next property
step 8: decrement the size property by 1 and return the list

Code implementation in Javascript :

   remove(index){
       if(index<0 || index >= this.size ) return undefined
       if(index === 0) return this.shift()
       if(index === this.size-1) return this.pop()
        let prevNode = this.get(index-1)
        let temp = prevNode.next
        prevNode.next = temp.next
        this.size--
        return this

   }

In python:

def remove(self,index):
         if index<0 or index>= self.size: return
         if index == 0:
             return self.shift()
         if index == self.size-1:
            return self.pop()
         prevNode = self.get(index-1)
         temp = prevNode.next
         prevNode.next = temp.next
         self.size-=1
         return self

Reverse

This method will reverse the direction of the list. The start will be the end and the end the new start. Basically, we will be starting from the end going backwards to the start.The steps to follow are outlined below

step 1 : Create a node variable and set it equal to head property
step 2: Set the head property to the tail property and the tail property to the node variable
step 3: Create a Next and prev variable and set them both to null or None.
step 4: Start a loop for when it is within the size property's range take 1 step from zero.
step 5: In each step set the Next variable to the current node's next property, set the current node's next property to the prev variable, set the prev variable to the current node and finally set the node variable to the Next variable.
step 6: Return the list

NB If you check the final solution there is an extra method called print, the method puts the values in an array in order and returns the array, I included it for testing the reverse method only, otherwise, it is not needed. If you print the list for the first time, it should return the list in the order entered, reverse the list and print again. the array returned should be in reverse to show the operation was successfull.
Code implementation in Javascript :

 reverse(){
       let node = this.head;
       this.head= this.tail;     // 20 -> 21 -> 22 -> 23
       this.tail = node;     // reversed           21 -> 20 -> null
       let Next,
           prev=null;
       for(let i =0;i< this.size;i++){
           Next= node.next
           node.next=prev
           prev = node
           node = Next        
       }
       return this

   }

In python:

def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node
        prev = Next =None
        for i in range(self.size):
            Next = node.next
            node.next = prev
            prev = node
            node = Next
            i+=1
        return self

Final Code solution for JavaScript :

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

    }
}

class SLL{
    constructor(){
        this.head= null
        this.tail= null
        this.size= 0

    }

    push(val){
        let newNode= new Node(val);
        if(!this.head){
            this.head=newNode
            this.tail= newNode
            this.size++
            return this
        }
        this.tail.next = newNode
        this.tail = newNode
        this.size++
        return this
    }
    pop(){
        if(!this.head) return undefined;
        let current= this.head;
        let newTail=current;
        while(current.next){
            newTail = current;
            current= current.next;
        }
        this.tail= newTail;
        this.tail.next= null;
        this.size--;
        if(this.size ===0){
            this.head = null;
            this.tail = null;
        }
        return this;
    }

   //shift
   shift(){
       if(!this.head) return undefined
       let temp = this.head;
       this.head = this.head.next;
       this.size --;
       if(this.size ===0){
           this.tail =null;
       }
       return temp
   }
   //unshift
   unshift(val){
       let newNode = new Node(val);
       if(!this.head){
           this.head= newNode;
           this.tail = newNode;
       }else{
           newNode.next = this.head;
           this.head = newNode;
       }
       this.size++;
       return this;


   }
   //get
   get(index){
       if(index<0 || index >= this.size)return undefined;
       let count=0;
       let current= this.head;
       while(count !== index){
           current= current.next;
           count++
       }
       return current;


   }
   //set
   set(index, val){
        let node = this.get(index);
        if(node){
            node.val = val;
            return true;
        }
        return false;
   }
   //insert
   insert(index, val){
       if(index<0 || index > this.size ) return undefined
       if(index === 0){
           this.unshift(val);
       }else if(index === this.size){
           this.push(val);
       }else{
           let newNode = new Node(val);
           let node  = this.get(index-1);
           let temp = node.next;
               node.next = newNode;
               newNode.next = temp;
       }

      this.size++;
      return this;

   }
   //remove
   remove(index){
       if(index<0 || index >= this.size ) return undefined
       if(index === 0) return this.shift()
       if(index === this.size-1) return this.pop()
        let prevNode = this.get(index-1)
        let temp = prevNode.next
        prevNode.next = temp.next
        this.size--
        return this

   }
   //reverse
   reverse(){
       let node = this.head;
       this.head= this.tail;     // 20 -> 21 -> 22 -> 23
       this.tail = node;     // reversed           21 -> 20 -> null
       let Next,
           prev=null;
       for(let i =0;i< this.size;i++){
           Next= node.next
           node.next=prev
           prev = node
           node = Next        
       }
       return this

   }

   //print
   print(){
       let current= this.head
       let arr = []
       while(current){
           arr.push(current.val)
           current = current.next
       }
       return arr
   }
}

let list =new SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)

for Python:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


class SLL:
    def __init__(self):
        self.head=None
        self.tail= None
        self.size=0

    def traverse_list(self):
        if(self.head is None):
            print("No elements in this list")
            return
        else:
            n = self.head
            while n is not None:
                print(n.val)
                n = n.next


    def push(self,val):
        newNode =  Node(val)

        if(self.head == None):
            self.head = newNode
            self.tail = newNode
        else:
            self.tail.next= newNode
            self.tail = newNode      
        self.size+=1
        return self

    def pop(self):
        if self.head ==None:return
        current = self.head
        new_tail = None
        while current.next is not None:
            new_tail = current
            current = current.next

        self.tail = new_tail
        self.tail.next = None
        self.size-=1
        if self.size == 0:
            self.head = None
            self.tail = None
        return self


    def shift(self):
        if self.head == None: return 
        temp = self.head
        self.head = self.head.next
        self.size-=1
        if(self.size == 0):
            self.tail = None
        return temp

    def unshift(self,val):
        newNode = Node(val)
        if self.head == None:
            self.head = newNode
            self.tail = newNode
        else:
            newNode.next = self.head
            self.head = newNode
        self.size+=1
        return self



    def get(self,index):
        if index <0 or index >=self.size:return
        current= self.head
        count = 0
        while count != index:
            current = current.next
            count+=1
        return current

    def set(self,index,val):
        node = self.get(index)
        if node :
            node.val = val
            return True
        return False


    def insert(self,index, val):
        if index<0 or index> self.size: return
        if index == 0: return self.unshift(val)
        if index == self.size: return self.push(val)
        newNode = Node(val)
        prevNode = self.get(index-1)
        temp = prevNode.next
        prevNode.next = newNode
        newNode.next = temp
        self.size+=1
        return self


    def remove(self,index):
         if index<0 or index>= self.size: return
         if index == 0:
             return self.shift()
         if index == self.size-1:
            return self.pop()
         prevNode = self.get(index-1)
         temp = prevNode.next
         prevNode.next = temp.next
         self.size-=1
         return self



    def print(self):
        arr=[]
        current= self.head
        while current:
            arr.append(current.val)
            current= current.next
        return arr


    def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node
        prev = Next =None
        for i in range(self.size):
            Next = node.next
            node.next = prev
            prev = node
            node = Next
            i+=1
        return self


list = SLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
print("|||||||||||||")

list.traverse_list
print("***************")
print(list.print())
print("===============")
list.reverse()
print("===============")
print(list.print())

Advantages Of Linked List:

1. Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.
2. No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-allocate the memory.
3. Implementation: Linear data structures like stack and queues are often easily implemented using a linked list. Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list. There is no need to shift elements after the insertion or deletion of an element only the address present in the next pointer needs to be updated.

Disadvantages Of Linked List:

1. Memory usage: More memory is required in the linked list as compared to an array. Because in a linked list, a pointer is also required to store the address of the next element and it requires extra memory for itself.
2. Traversal: In a Linked list traversal is more time-consuming as compared to an array. Direct access to an element is not possible in a linked list as in an array by index. For example, for accessing a mode at position n, one has to traverse all the nodes before it.
3. Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case of a doubly-linked list, it can be possible as it contains a pointer to the previously connected nodes with each node. For performing this extra memory is required for the back pointer hence, there is a wastage of memory.
4. Random Access: Random access is not possible in a linked list due to its dynamic memory allocation.

Conclusion

The implementation of a linked list is language agnostic, once you understand the logic behind it, you can implement it with any language of your choosing.Just follow the steps outlined above.