Oct 16, 2021

10 min read

Data Structures in Python: LinkedList

Before starting today’s tutorial if you to know what are previous topics before the linked list that I have taught in Data Structures scroll down to the bottom. Links are available there

A linked list is an ordered collection of objects which are connected via links. Each element of the linked list is called a node. Each node consists of two elements-

Data: It contains the value
Next: It contains the address of the next node of the list

The node looks something like this:

So, a linked list is a collection of nodes.

In the above figure representing a linked list notice that the first element has a head arrow which means the first element of the node is called head and it is used for iterating through the linked list. Also notice that in the last element next is none as there is no next element after the last element and it is used for ending the iteration.

The linked list is not a built-in data structure in Python but we can create it through the concept of node

So far what I have taught you about the linked list is more precisely a singly linked list and in this lecture, I will be implementing a singly linked list. There is one more type called doubly linked list which we will study later.

Creating Linked list

We will create a node object and create another class to use this node object:

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

Here in the above code, we created a node object and in this node, we have data and next element address attributes.

Now let's create a LinkedList class to use this node object:

class LinkedList:
    def __init__(self):
        self.head = None

Now let's use the above codes to create our linked list

LL = LinkedList()
LL.head = Node("Sun") #here we created head with node data "Sun"print(LL)#OUTPUT
Sun

Now let's create more nodes and connect them:

e2 = Node("Mon") #2nd node
e3 = Node("Tue") #3rd node#let's connect head to e2 node
LL.head.next = e2#e2 to e3
e2.next = e3print(LL)#OUTPUT:
<__main__.LinkedList object at 0x000001ffe570dfd0>

Here above when we printed our linked list a linked list object is returned. Instead of this object if you want to show list values then we should traverse through our linked list and show every node value until the next value of the node is none.

Traversing

We will implement our traverse code in the __repr__ method.

class LinkedList:
    def __init__(self):
        self.head = None    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listr

In the ‘ __repr__’ method first, check if the head node is present because if the head is None then just show “Empty Linked List”.

We iterated through the linked list using the while loop until the next element of the current node is none and break the loop.

print(LL)#OUTPUT
Sun->Mon->Tue

I hope this would be enough for today and we will continue this only lecture tomorrow where we will implement insertion and deletion.

Insertion

Insertion could be of many types like:

Insert at beginning
Insert at end
Insert at some specific position as we do in the list using the index and value
Insert after element
Inserting list of values

Insert at the beginning:

Inserting at the beginning of the linked list is too simple, just create a new node you want to insert with next equal to the current head node and define that node as a head node.

class LinkedList:
    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrLL.insert_at_beginning("Fri")
print(LL)#OUTPUT
Fri->Sun->Mon->Tue

Insert at the end:

First of all, we will check if there is an element in our list by checking the head if it's empty then we will create a node and assign the head to it otherwise we will iterate as done in traversing and insert at the end.

class LinkedList:    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def insert_at_end(self, data): #Inserting at the end
        if self.head is None:
            self.head = Node(data, None)
            return
    
        itr = self.head        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrLL.insert_at_end("Thu")
print(LL)#OUTPUT
Fri->Sun->Mon->Tue->Thu

Inserting Data List

To insert a list of values we have to iterate through the list inserted and add elements to the end of the linked list using the insert_at_end method.

class LinkedList:    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def insert_at_end(self, data): #Inserting at the end
        if self.head is None:
            self.head = Node(data, None)
            return
    
        itr = self.head        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)
    def insert_values(self, data_list): #Inserting data list
        self.head = None        for data in data_list:
            self.insert_at_end(data)
    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrLL = LinkedList()
LL.insert_values([1, 2, 3, 4, 5])
print(LL)#OUTPUT
1->2->3->4->5

Get length of linked list

Before going further in insertion we will implement the get_len method to get the length of the list

class LinkedList:    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def insert_at_end(self, data): #Inserting at the end
        if self.head is None:
            self.head = Node(data, None)
            return
    
        itr = self.head        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)    def insert_values(self, data_list): #Inserting data list
        self.head = None        for data in data_list:
            self.insert_at_end(data)
    def get_len(self): #get the length of the list
        count = 0        itr = self.head
        while itr:
            count += 1
            itr = itr.next
        return count    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrprint(LL.get_len())#OUTPUT
5

Insert at Index

We will create the insert_at method where we will pass the index and data value we want to insert.

class LinkedList:    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def insert_at_end(self, data): #Inserting at the end
        if self.head is None:
            self.head = Node(data, None)
            return
    
        itr = self.head        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)    def insert_values(self, data_list): #Inserting data list
        self.head = None        for data in data_list:
            self.insert_at_end(data)    def get_len(self): #get the length of the list
        count = 0        itr = self.head
        while itr:
            count += 1
            itr = itr.next
        return count    def insert_at(self, index, data): #to insert at particular index
        if index<0 or index>=self.get_len():
            raise Exception("Invalid index")        if index == 0:
            self.insert_at_begining(data)        count = 0
        itr = self.head        while itr:#iterate until element is found
            if count == index -1:
                node = Node(data, itr.next)
                itr.next = node
                break
            itr = itr.next
            count += 1    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrLL.insert_at(2, 6)
print(LL)#OUTPUT
1->2->6->3->4->5

Insert after value

To insert a node after a particular node let’s create the insert_after method:

class LinkedList:    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def insert_at_end(self, data): #Inserting at the end
        if self.head is None:
            self.head = Node(data, None)
            return
    
        itr = self.head        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)    def insert_values(self, data_list): #Inserting data list
        self.head = None        for data in data_list:
            self.insert_at_end(data)    def get_len(self): #get the length of the list
        count = 0        itr = self.head
        while itr:
            count += 1
            itr = itr.next
        return count    def insert_at(self, index, data): #to insert at particular index
        if index<0 or index>=self.get_len():
            raise Exception("Invalid index")        if index == 0:
            self.insert_at_begining(data)        count = 0
        itr = self.head        while itr:#iterate until element is found
            if count == index -1:
                node = Node(data, itr.next)
                itr.next = node
                break
            itr = itr.next
            count += 1
    
    #Insert after a value    def insert_after_value(self, data_after, data_to_insert):
        itr = self.head
        while itr:
            if itr.data == data_after:
                node = Node(data_to_insert, itr.next)
                itr.next = node
                return
            itr = itr.next
        return None    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrLL.insert_after_value(1, 8)
print(LL)#OUTPUT
1->8->2->6->3->4->5

Removing Nodes

We may want to remove nodes using index or value

Remove using Index

We will iterate through the list and remove value when reached the index value

class LinkedList:    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def insert_at_end(self, data): #Inserting at the end
        if self.head is None:
            self.head = Node(data, None)
            return
    
        itr = self.head        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)    def insert_values(self, data_list): #Inserting data list
        self.head = None        for data in data_list:
            self.insert_at_end(data)    def get_len(self): #get the length of the list
        count = 0        itr = self.head
        while itr:
            count += 1
            itr = itr.next
        return count    def insert_at(self, index, data): #to insert at particular index
        if index<0 or index>=self.get_len():
            raise Exception("Invalid index")        if index == 0:
            self.insert_at_begining(data)        count = 0
        itr = self.head        while itr:#iterate until element is found
            if count == index -1:
                node = Node(data, itr.next)
                itr.next = node
                break
            itr = itr.next
            count += 1
    
    #Insert after a value    def insert_after_value(self, data_after, data_to_insert):
        itr = self.head
        while itr:
            if itr.data == data_after:
                node = Node(data_to_insert, itr.next)
                itr.next = node
                return
            itr = itr.next
        return None    def remove_at(self, index):        if index<0 or index>=self.get_len():
            raise Exception("Invalid index")        if index == 0:
            self.head = self.head.next
            return
        
        count = 0
        itr = self.head
        while itr:
            if count == index - 1:
                itr.next = itr.next.next
                break
            itr = itr.next
            count += 1    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrLL.remove_at(1)
print(LL)#OUTPUT
1->2->6->3->4->5

Remove by Value

class LinkedList:    def __init__(self):
        self.head = None    def insert_at_beginning(self, data):#Insertion at beginning
        node = Node(data, self.head)
        self.head = node    def insert_at_end(self, data): #Inserting at the end
        if self.head is None:
            self.head = Node(data, None)
            return
    
        itr = self.head        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)    def insert_values(self, data_list): #Inserting data list
        self.head = None        for data in data_list:
            self.insert_at_end(data)    def get_len(self): #get the length of the list
        count = 0        itr = self.head
        while itr:
            count += 1
            itr = itr.next
        return count    def insert_at(self, index, data): #to insert at particular index
        if index<0 or index>=self.get_len():
            raise Exception("Invalid index")        if index == 0:
            self.insert_at_begining(data)        count = 0
        itr = self.head        while itr:#iterate until element is found
            if count == index -1:
                node = Node(data, itr.next)
                itr.next = node
                break
            itr = itr.next
            count += 1
    
    #Insert after a value    def insert_after_value(self, data_after, data_to_insert):
        itr = self.head
        while itr:
            if itr.data == data_after:
                node = Node(data_to_insert, itr.next)
                itr.next = node
                return
            itr = itr.next
        return None    def remove_at(self, index):        if index<0 or index>=self.get_len():
            raise Exception("Invalid index")        if index == 0:
            self.head = self.head.next
            return
        
        count = 0
        itr = self.head
        while itr:
            if count == index - 1:
                itr.next = itr.next.next
                break
            itr = itr.next
            count += 1    def remove_by_value(self, data):
        if self.head == None:
            return        if self.head.data == data:
            self.head = self.head.next
            return        itr = self.head
        while itr:
            if itr.next.data == data:
                itr.next = itr.next.next
                return
            itr = itr.next
        return None    def __repr__(self):
        if self.head is None:
            return "Empty Linked List"
        itr = self.head
        listr = ''        while itr:
            if itr.next == None:
                listr += str(itr.data)
                break
            listr += str(itr.data) + '->'
            itr = itr.next
            return listrLL.remove_by_value(4)
print(LL)#OUTPUT
1->2->6->3->5

That will be enough for this tutorial. If you are confused why I haven’t taught Big O notation in the linked list don’t worry it will be covered in coming tutorials. Also, I don’t want to confuse you by including everything at once. So, don’t worry and have a good day!