Linked Lists

The most commonly used data structure; arrays, had quite an influence on computation and programming over the years but other data structures are working under the hood to keep the pillars of computation standing and I would be explaining one of those data structures; the linked list.

Being one of the most commonly used data structures, you might have heard of or encountered the Linked List data structure. Linked Lists are the most popular data structure after arrays; they have contributed a lot to computation and you can find them in almost every digital system architecture. So, the big question is what are Linked Lists? I bet you have been hearing a lot about them but in this article, I’ll be explaining the types, their implementation and how they can be used in your project.

Definition

A Linked List is a linear data structure where each node contains a pointer to the next or previous node in its sequence.

A graphical representation:

Types Of Linked Lists

Singly Linked List:

• This is a type of linked list where the pointer goes in one direction, which is usually forward. Each node references the next node in front of it but the one in the front can't reference the ones behind.

• Example:

• 

Implementation

To implement the singly Linked List data structure we would start with creating a node class for all the nodes that would be in the linked list. The node class of a singly linked list has three important attributes which are the 'value' which points to the node's value, the 'next' attribute which has a reference to the next node in the structure and the 'index' which stores the position of each node in the structure.

Your Node Class:

class Node:
    def __init__(self,value,next,index):
      self.value=value
      self.next=next
      self.index=index

The next step is to create the singly linked list structure itself; the singly linked class is used to arrange the nodes in a particular pattern i.e. the singly linked list pattern. The class has two attributes which are the 'list' attribute which contains all the nodes and the 'length' attribute which contains the length of the linked list.

The Singly Linked Class:

class SinglyLinked:
   def __init__(self):
      self.list=None
      self.length=0

After creating the singly linked class we need to create some methods that would make the class functional, and one of those methods is the insert method which inserts nodes into the 'list' attribute.

The Insert Method:

def insert(self,value):
      node=Node(value,self.list,self.length) 
      self.list=node
      self.length+=1

The insert method is the most compulsory method a Linked List ought to have because it is what adds new elements to the Linked List, but I'll be adding a few more methods that will be used in the Linked List such as print(),getIndex(), and remove() methods etc.

The getIndex Method:

 def getIndex(self,index):
      data=self.list
      ans='Index Not Found'
      while data:
         if data.index==index:
            ans=data
            break
         else:
            data=data.next
      return ans

This method is used to get an individual node at a given index and it finds them using the node's index attribute and a while loop that iterates through the linked lists. The data variable is used to clone the Linked List collection by assigning it to the self.list attribute of the class; the reason why we clone the collection is to prevent it from being tampered with during the iteration. The while loop runs while data is not null, remember the last element of the Singly Linked List is null; so, once data is null it means we have reached the end of the list. The if statement is used to check whether the current data index attribute is equal to the index we are searching for, if the condition is then satisfied we assign the ans variable to the current data and break the while loop, else the current data would be set to the next node. When the loop finishes running it returns the value of the ans variable.

The find() Method:

This method is similar to the getIndex method, but it has a slight difference. The getIndex() method tries to match the index of the list nodes while the find() method tries to match the values of the nodes. It is used to check if a node is present in the linked list.

  def find(self,val):
      data=self.list 
      ans='Not Found'   
      while data:
         if data.value==val:
            ans='Found'
            break
         else:
            data=data.next
      return ans

The remove() Method:

This method is the most complex of the previous methods but it is easy to understand, trust me. First of all, we need to create a helper method in our Node Class named delete(); this method would be used to set the next node of an individual node to its next next node😆 Confused right? let me explain. For example, we have a node named A and its next node is B and the next node of B is C, when the delete() method is called on A it would set B to become C. Easy stuff!

class Node:
    def __init__(self,value,next,index):
      self.value=value
      self.next=next
      self.index=index
    def delete(self):
      self.next=self.next.next

This is just the first part of the remove() method.

The remove() would be written in the Singly Linked Class and it would be used to remove nodes by getting the index of the previous node and calling the delete method on it. Hurray! 😸

Then we use a while loop to decrement the index of every node lesser than the node's index.

  def remove(self,index):
      self.getIndex(index+1).delete()
      while data:
         if data.index<index:
            break
         data.index-=1
         data=data.next

Now this is what your code should look like:

class Node:
    def __init__(self,value,next,index):
      self.value=value
      self.next=next
      self.index=index
    def delete(self):
      self.next=self.next.next

class SinglyLinked:
   def __init__(self):
      self.list=None
      self.length=0

   def insert(self,value):
      node=Node(value,self.list,self.length)
      self.list=node
      self.length+=1

   def find(self,val):
      data=self.list 
      ans='Not Found'   
      while data:
         if data.value==val:
            ans='Found'
            break
         else:
            data=data.next
      return ans

   def getIndex(self,index):
      data=self.list
      ans='Index Not Found'
      while data:
         if data.index==index:
            ans=data
            break
         else:
            data=data.next
      return ans

   def remove(self,index):
      self.getIndex(index+1).delete()
      while data:
         if data.index<index:
            break
         data.index-=1
         data=data.next

   def print(self):
      data=self.list
      res=''
      while data:
         res+=f'{data.index}->{data.value } \n'
         data=data.next
      return print(res)

Doubly Linked List:

This is a type of Linked List where each node has two references, one to the node in its front and the other to the node behind.

Implementation

To implement the Doubly Linked List data structure we would start with creating a node class for all the nodes that would be in the linked list. The node class of a doubly linked list has four important attributes which are the 'value' which points to the node's value, the 'next' attribute which has a reference to the next node in the structure, the 'prev' attribute which has a reference to the previous node in the structure and the 'index' which stores the position of each node in the structure.

The Node Class:

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

The next step is to create the doubly linked list structure itself; the doubly linked class is used to arrange the nodes in the doubly linked pattern just as we did in the Singly Linked List implementation above.

class DoublyLinked:
    def __init__(self):
        self.head=None
        self.length=0

We would be repeating the same methods we used in the Singly Linked List here but there would be a little variation in the insert() of the Doubly Linked List.

insert() Method:

def insert(self,value):
        node= Node(value,self.head,None,self.length)
        if self.head:
            self.head.prev=node
        self.head=node
        self.length+=1

Just like the Singly Linked List(SLL) we, first of all, instantiate the node class in our method and in the previous parameter we set it to "None"; then we make a conditional that checks if the head is not null so that we can set the current node's prev attribute to the node about to be inserted.

Every other method except the remove() from here henceforth follows the same pattern as the SLL methods, so make sure you read the explanations of the SLL methods above.

find() Method:

  def find(self,val):
      data=self.head
      ans='Not Found'   
      while data:
         if data.val==val:
            ans='Found'
            break
         else:
            data=data.next
      return ans

No variations 😁

getIndex() Method:

  def getIndex(self,index):
       data=self.head
       while data:
          if data.index==index:
             break
          else:
             data=data.next
       if data:
        return data
       else:
          return 'Index Not Found'

print() Method:

  def print(self):
        data=self.head
        listed=''
        while data:
            if data.next:
             if data.prev:
              listed+=f'''
                ---------------
                next: {data.next.val}
                value:{data.val}
                prev: {data.prev.val}
                ------------------
                    |
                   \ /
                '''
             else:
                listed+=f'''
                ---------------
                next: {data.next.val}
                value:{data.val}
                prev: Null
                ------------------
                    |
                   \ /
                '''
            else:
                listed+=f'''
                   / \
                    |
                ---------------
                next: Null
                value:{data.val}
                prev:{data.prev.val}
                ------------------
                '''
            data=data.next
        return print(listed)

Not minding all the long lines of codes in this method, this method is super easy all it does is traverse through the list with a while loop that checks if the current node is null, because if it is that means we are at the end of the list. That's why data is set to data.next at every iteration.

remove() Method:

Just like the SLL we would go to the node class and create the delete method; this is where the variation is. Remember in the SLL class we were setting the next node to its next node because it is one-dimensional, but the Doubly Linked List on the other hand is two dimensional that is we would be setting the next node to its next node and we would be setting that next next node's previous attribute to the node calling the method. Ughhh! 😣 Pretty complicated right? Look at the implementation and you'll understand.

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

    def delete(self):
      self.next=self.next.next
      self.next.prev=self #the next next node's prev attribute

The remove() method used in the DLL class remains the same as its SLL counterpart.

def remove(self,index):
      self.getIndex(index+1).delete()
      data=self.head
      self.length-=1
      while data:
         if data.index<index:
            break
         data.index-=1
         data=data.next

The End Result

Your code should look like this:

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

    def delete(self):
      self.next=self.next.next
      self.next.prev=self


class DoublyLinked:
    def __init__(self):
        self.head=None
        self.length=0
    def insert(self,value):
        node= Node(value,self.head,None,self.length)
        if self.head:
            self.head.prev=node
        self.head=node
        self.length+=1
    def print(self):
        data=self.head
        listed=''
        while data:
            if data.next:
             if data.prev:
              listed+=f'''
                ---------------
                next: {data.next.val}
                value:{data.val}
                prev: {data.prev.val}
                ------------------
                    |
                   \ /
                '''
             else:
                listed+=f'''
                ---------------
                next: {data.next.val}
                value:{data.val}
                prev: Null
                ------------------
                    |
                   \ /
                '''
            else:
                listed+=f'''
                   / \
                    |
                ---------------
                next: Null
                value:{data.val}
                prev:{data.prev.val}
                ------------------
                '''
            data=data.next
        return print(listed)
    def find(self,val):
      data=self.head
      ans='Not Found'   
      while data:
         if data.val==val:
            ans='Found'
            break
         else:
            data=data.next
      return ans
    def getIndex(self,index):
       data=self.head
       while data:
          if data.index==index:
             break
          else:
             data=data.next
       if data:
        return data
       else:
          return 'Index Not Found'

    def remove(self,index):
      self.getIndex(index+1).delete()
      data=self.head
      self.length-=1
      while data:
         if data.index<index:
            break

         data.index-=1
         data=data.next





test=DoublyLinked()
test.insert(2)
test.insert(3)
test.insert(5)
test.insert(6)
test.insert(8)
test.remove(3)
test.print()

'''
result:
      ---------------
                next: 5
                value:8
                prev: Null
                ------------------
                    |
                   \ /

                ---------------
                next: 3
                value:5
                prev: 8
                ------------------
                    |
                   \ /

                ---------------
                next: 2
                value:3
                prev: 5
                ------------------
                    |
                   \ /


                ---------------
                next: Null
                value:2
                prev:3
                ------------------


'''

Satisfying 😻

Circular Linked List:

This Linked List is a variation of the Singly Linked List. Each node in a circular linked list has a pointer to the next node including the last node which has a pointer to the first node of the list.

Implementation

The Circular Linked List(CLL) is very much similar to the Singly Linked List(SLL) but it varies in methods that use while loops because nodes can never be null meaning that the loop can't be broken by the null condition because in the CLL the next pointer at the last node points to the first and keeps it infinitely linked like a ring. So, we use a different approach to break the loops by setting a conditional that checks if the node's index is 0.

Node Class:

class Node:
    def __init__(self,value,next,index):
      self.value=value
      self.next=next
      self.index=index

    def delete(self):
      self.next=self.next.next

insert() Method:

class CircularLinked:
   def __init__(self):
      self.list=None
      self.length=0

   def insert(self,value):
      node=Node(value,self.list,self.length)
      self.list=node
      self.length+=1
      first=self.getIndex(0)
      first.next=node

   def getIndex(self,index):
      data=self.list

      while data:
         if data.index==index:
            break
         if data.index==0:
            break
         else:
            data=data.next 
      if data.index==index:
       return data
      else:
         return 'Index Not Found'

To set the first node's next attribute to the last node we use the getIndex() method to fetch the first node and set its next attribute to the node currently being inserted at the moment the insert() method is called.

Every other method remains the same except for the break loop condition when the node index is 0.

The Code Results:

class Node:
    def __init__(self,value,next,index):
      self.value=value
      self.next=next
      self.index=index

    def delete(self):
      self.next=self.next.next

class CircularLinked:
   def __init__(self):
      self.list=None
      self.length=0

   def insert(self,value):
      node=Node(value,self.list,self.length)
      self.list=node
      self.length+=1
      first=self.getIndex(0)
      first.next=node


   def find(self,val):
      data=self.list
      ans='Not Found'   
      while data:
         if data.value==val:
            ans='Found'
            break
         else:
            data=data.next
      return ans
   def remove(self,index):
      self.getIndex(index+1).delete()

   def getIndex(self,index):
      data=self.list

      while data:
         if data.index==index:
            break
         if data.index==0:
            break
         else:
            data=data.next 
      if data.index==index:
       return data
      else:
         return 'Index Not Found'

   def print(self):
      data=self.list
      string='\n Circular Linked List'
      while data:
         if data.index== (0):
            string+=f'''
        ------------------------- 
        index:{data.index}
        value: {data.value}
        next:({data.next.value})
        -------------------------
        '''
            break

         else:
             string+=f'''
        ------------------------- 
        index:{data.index}
        value: {data.value}
        next:({data.next.value})
        -------------------------
         |
        \ /
        '''
             data=data.next
      return print(string)


test=CircularLinked()
test.insert(3)
test.insert(13)
test.insert(23)
test.insert(33)
test.insert(43)
test.print()

'''
Result:

 Circular Linked List
        -------------------------
        index:4
        value: 43
        next:(33)
        -------------------------
         |
        \ /

        -------------------------
        index:3
        value: 33
        next:(23)
        -------------------------
         |
        \ /

        -------------------------
        index:2
        value: 23
        next:(13)
        -------------------------
         |
        \ /

        -------------------------
        index:1
        value: 13
        next:(3)
        -------------------------
         |
        \ /

        -------------------------
        index:0
        value: 3
        next:(43)
        -------------------------

'''

Double Circular Linked List:

This is a variation of the doubly linked list where every node has a pointer to its previous and next node including the first and the last node which have references to each other.

Implementation

It is just like the Doubly Linked List in a circular format. Its methods are similar to the DLL methods but like the SCLL it has the 0 node index conditional for breaking the loops and its insert method is similar to the SCLL's insert method.

class Node:
     def __init__(self,val,next,prev,index):
        self.value=val
        self.next=next
        self.prev=prev
        self.index=index

     def delete(self):
      self.next=self.next.next
      self.next.prev=self


class CircularLinked:
   def __init__(self):
      self.list=None
      self.length=0

   def insert(self,value):
      node=Node(value,self.list,None,self.length)
      if self.list:
            self.list.prev=node
      self.list=node
      self.length+=1
      first=self.getIndex(0)
      first.next=node
      self.list.prev=first

   def find(self,val):
      data=self.list
      ans='Not Found'   
      while data:
         if data.value==val:
            ans='Found'
            break
         else:
            data=data.next
      return ans

   def getIndex(self,index):
      data=self.list

      while data:
         if data.index==index:
            break
         if data.index==0:
            break
         else:
            data=data.next 
      if data.index==index:
       return data
      else:
         return 'Index Not Found'
   def remove(self,index):
      self.getIndex(index+1).delete()

   def print(self):
      data=self.list
      string='\nDOUBLY CIRCULAR LINKED LIST'
      while data:
        if data.index!=0:
         string+=f'''
        -------------------------
        prev: ({data.prev.value})
        index: {data.index}
        value: {data.value}
        current ({data.next.value})
        -------------------------
         |
        \ /
        '''
        if data.index==0:
            string+=f'''
        ------------------------
        prev: ({data.prev.value})
        index: {data.index}
        value: {data.value}
        next: ({data.next.value})
        ---------------------------
        '''
            break


        data=data.next
      return print(string)
   def remove(self,index):
      self.getIndex(index+1).delete()

      self.length-=1



test=CircularLinked()
test.insert(3)
test.insert(13)
test.insert(23)
test.insert(33)
test.insert(43)
test.print()

'''
Result:

DOUBLY CIRCULAR LINKED LIST
        -------------------------
        prev: (3)
        index: 4
        value: 43
        current (33)
        -------------------------
         |
        \ /

        -------------------------
        prev: (43)
        index: 3
        value: 33
        current (23)
        -------------------------
         |
        \ /

        -------------------------
        prev: (33)
        index: 2
        value: 23
        current (13)
        -------------------------
         |
        \ /

        -------------------------
        prev: (23)
        index: 1
        value: 13
        current (3)
        -------------------------
         |
        \ /

        ------------------------
        prev: (13)
        index: 0
        value: 3
        next: (43)
        ---------------------------

'''

This is just an excerpt from my GitHub Repo on Data Structures and Algorithms, I will be dropping detailed explanations of other data structures and algorithms on the repo.

Stay Tuned, Thank You.