# 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-

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.

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)#OUTPUTSun`

Now let's create more nodes and connect them:

`e2 = Node("Mon") #2nd nodee3 = Node("Tue") #3rd node#let's connect head to e2 nodeLL.head.next = e2#e2 to e3e2.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)#OUTPUTSun->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 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)#OUTPUTFri->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)#OUTPUTFri->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)#OUTPUT1->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())#OUTPUT5`

## 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)#OUTPUT1->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)#OUTPUT1->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)#OUTPUT1->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)#OUTPUT1->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!

--

--