Linked List Made Easy

In this notebook, we will understand and build Linked List from scratch. We will build it step-by-step after understanding its core concepts. I will also perform testing and debugging of the code to show how we read errors, understand and debug them. This is going to be a long blog but quick to read since most of the code is copy pasted multiple times within the notebook.

# type hints
from typing import List, Union

A Linked List is made up of nodes, where nodes contain data and a pointer to the next node.

Let’s create a Node class which will have 2 attributes: data & a pointer to the next node

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

Let’s build a LinkedList in baby steps.

First, we will build 2 functions in linked list. One to create a linked list by adding data and another to print it so that we can visualize and debug.

class LinkedList:
    def __init__(self):
        pass

    def insert_at_beginning(self, data):
        pass

    def print(self):
        pass

Once we build the above class with 2 simple functions - insert_at_beginning and print, it will be much simpler to complete the remaining functions to add different functionalities to LinkedList

class LinkedList:
    def __init__(self):
        pass

    def insert_at_beginning(self, data):
        pass

    def print(self):
        pass

    def insert_at_end(self, data):
        pass

    def insert_values(self, data_list):
        pass

    def get_length(self):
        pass

    def insert_at(self, index):
        pass

    def remove_at(self, index):
        pass

It is important to realize whether inputs are required for creating any function. If not, why not. If yes, what type of inputs.

Let’s get started.

Concepts:

We will add data by creating Nodes.
We use head to control any operation on Linked List we want to perform.

head is an object always pointing towards the start of the linked list. (head means top/start)

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added       

    def print(self):
        # to print we iterate on the node starting from the first node
        itr = self.head
        if itr.data is None:
            print("Linked List is empty")
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

# Let's test the code we created so far by creating a linked list and adding elements at the beginning
ll = LinkedList()
ll.insert_at_beginning(292)
ll.insert_at_beginning(301)
ll.print()

301-->292-->

# let's test for an edge case of empty list
ll = LinkedList()
ll.print()

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[11], line 3
      1 # let's test for an edge case of empty list
      2 ll = LinkedList()
----> 3 ll.print()

Cell In[9], line 15, in LinkedList.print(self)
     12 def print(self):
     13     # to print we iterate on the node starting from the first node
     14     itr = self.head
---> 15     if itr.data is None:
     16         print("Linked List is empty")
     17     llstr = ""

AttributeError: 'NoneType' object has no attribute 'data'

We are getting an AttributeError because we are trying to refer an attribute data that does not even exist for an empty list. So, issue is for an empty list. It is so because empty list contains None element as head (self.head = None). You can see the topmost figue in insert at beginning. This None head does not have data attribute.

So, we need to change the code slightly and condition over the self.head to check for an empty list

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added       

    def print(self):        
        # edge case: if ll is empty
        if self.head is None:
            print("Linked List is empty!")
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

# let's test for an edge case of empty list
ll = LinkedList()
ll.print()

Linked List is empty!

Great! this works as expected. Now, let’s add insert_at_end

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added      

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data):
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

In print I used while itr:, whereas in insert_at_end, I used while itr.next. Draw a diagram and think why this makes sense.

In fact, print could be rewritten as:

def print(self):
    # edge case
    itr = self.head
    if itr.data is None:
        print("Linked List is empty")
    llstr = ""
    while itr.next: 
        llstr+=str(itr.data)
        llstr+='-->'
        itr = itr.next
    # above code end by reaching the last node
    llstr+=str(itr.data) # add data about the last node
    print(llstr)

# Let's test the code we created so far:
ll = LinkedList()
ll.insert_at_beginning(292)
ll.insert_at_beginning(301)
ll.insert_at_end(512)
ll.print()

301-->292-->512-->

Now let’s code insert_values - which creates a new linked list from the values given as a list.

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added      

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_beginning function
        for data in data_list:
            self.insert_at_beginning(data)

# Let's test the code we created so far:
ll = LinkedList()
ll.insert_at_beginning(292)
ll.insert_at_beginning(301)
ll.insert_at_end(512)
ll.print()
new_data_list = [1,3,5,7,9]
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()

301-->292-->512-->
9-->7-->5-->3-->1-->

Oops! it added elements in reverse order because we used insert_at_beginning. To correct this, there are 2 options: 1. reverse the data_list and use insert_at_beginning: not recommended because it creates computational burden of reversing the list 2. modify the code to use insert_at_end

Method-1:reverse the data_list and use insert_at_beginning

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_beginning function
        data_list = data_list[::-1] # reverse it
        for data in data_list:
            self.insert_at_beginning(data)

# Let's test the code we created so far:
new_data_list = [1,3,5,7,9]
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()

1-->3-->5-->7-->9-->

Method-2: Modify the code and use insert_at_end

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added    

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_end function
        for data in data_list:
            self.insert_at_end(data)

# Let's test the code we created so far:
new_data_list = [1,3,5,7,9]
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[21], line 4
      2 new_data_list = [1,3,5,7,9]
      3 ll = LinkedList()
----> 4 ll.insert_values(new_data_list)
      5 ll.print()

Cell In[20], line 41, in LinkedList.insert_values(self, data_list)
     39 # Use the insert_at_end function
     40 for data in data_list:
---> 41     self.insert_at_end(data)

Cell In[20], line 27, in LinkedList.insert_at_end(self, data)
     24 def insert_at_end(self, data:  Union[str, int]):
     25     # Remember - we use head as the iterator
     26     itr = self.head # start from the beginning of the list
---> 27     while itr.next:
     28         itr = itr.next # reach the end
     29     # once we reach end, do 2 things:
     30     # 1. make the node of new data and point it to None because it is the end

AttributeError: 'NoneType' object has no attribute 'next'

Oops! we got an error! This error is similar to what we saw earlier in print function.

We can see that it arises insert_at_end function. So, to debug, first inspect the insert_at_end for edge case of an empty list

ll = LinkedList()
ll.insert_at_end(23)
ll.print()

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[22], line 2
      1 ll = LinkedList()
----> 2 ll.insert_at_end(23)
      3 ll.print()

Cell In[20], line 27, in LinkedList.insert_at_end(self, data)
     24 def insert_at_end(self, data:  Union[str, int]):
     25     # Remember - we use head as the iterator
     26     itr = self.head # start from the beginning of the list
---> 27     while itr.next:
     28         itr = itr.next # reach the end
     29     # once we reach end, do 2 things:
     30     # 1. make the node of new data and point it to None because it is the end

AttributeError: 'NoneType' object has no attribute 'next'

Now we see the error! Earlier we did not see it because we used insert_at_end to a non-empty Linked List.

ll = LinkedList()
ll.insert_at_beginning(292)
ll.insert_at_beginning(301)
ll.insert_at_end(512) # -> adding at the end to a non-empty list and that's why we didn't see this error
ll.print()

It is always a good idea to try visualize what would be happening, if linked list is empty or has 1 element. Then the mental visualization can be extended into a code smoothly for n numbers of elements.

Perhaps this could help you visualize:

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added  

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # if linked list is empty, we simply add the node and make it as head
        if self.head is None:
            node = Node(data, None) # create a node and point it to None because it is end
            self.head = node        # make this node as new head so that we could iterate later

        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_end function
        for data in data_list:
            self.insert_at_end(data)


ll = LinkedList()
ll.insert_at_end(23)
ll.print()

23-->23-->


ll = LinkedList()
ll.insert_at_end(23)
ll.insert_at_end(43)
ll.print()

23-->23-->43-->

Here we see the first element getting repeated twice! Why?

Because initially, when the Linked List is empty! we added the element but then we did not stop the code after adding the new node to run.

Simply - To do so, add a return statement

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added    

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
            return # if linked list is empty, no need to run the below code. So, return
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # if linked list is empty
        if self.head is None:
            node = Node(data, None) # create a node and point it to None because it is end
            self.head = node        # make this node as new head (because until now there is no head i.e. linked list is empty)
            return # to stop the below code from running after adding the node to an empty Linked List
        
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_end function
        for data in data_list:
            self.insert_at_end(data)

ll = LinkedList()
ll.insert_at_end(23)
ll.print()

ll = LinkedList()
ll.insert_at_end(23)
ll.insert_at_end(43)
ll.print()

23-->
23-->43-->

Now, let’s test it for insert_values

# Let's test the code we created so far:
new_data_list = [1,3,5,7,9]
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()

1-->3-->5-->7-->9-->

Let’s now complete the code for LinkedList class.

Some helpful images for visualization for:

`insert_at`

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added    

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
            return # if linked list is empty, no need to run the below code. So, return
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # if linked list is empty
        if self.head is None:
            node = Node(data, None) # create a node and point it to None because it is end
            self.head = node        # make this node as new head (because until now there is no head i.e. linked list is empty)
            return # to stop the below code from running after adding the node to an empty Linked List
        
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_end function
        for data in data_list:
            self.insert_at_end(data)
    
    def get_length(self):
        counter = 0
        # Edge case: if linked list is empty. Then we need to check the `head`
        if self.head is None:
            return 0
        # else, iterate over head
        itr = self.head
        while itr:
            itr = itr.next
            counter+=1
        return counter
    
    def insert_at(self, index: int, data: Union[str, int]):
        # Edgecases: adding element at the start, or at the end 
        if index==0:
            self.insert_at_beginning(data)
        elif index == self.get_length():
            self.insert_at_end(data)
        if index<0 or index>self.get_length():
            raise Exception("Out of range")
        # By now, we are adding element in a non-empty list and somewhere in the middle
        # begin from the head (i.e. start of a lInked list)
        itr = self.head
        counter = 0
        while counter<index-1:
            itr = itr.next
            counter+=1
        # above loop will break as soon as we are at node just before where we want to add the new data
        # now add new data as a node and pointing to the next node in the original linked list
        node = Node(data, itr.next)
        # now point the previous node's next pointer to the new node just added
        itr.next = node

# Let's test the code for get_length:
new_data_list = [1,3,5,7,9]
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
print(ll.get_length())

new_data_list = [1]
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
print(ll.get_length())

ll = LinkedList()
ll.print()
print(ll.get_length())

ll = LinkedList()
ll.insert_at_beginning(23)
ll.print()
print(ll.get_length())

ll = LinkedList()
ll.insert_at_end(23)
ll.print()
print(ll.get_length())

1-->3-->5-->7-->9-->
5
1-->
1
Linked List is empty
0
23-->
1
23-->
1

# Let's test the code for insert_at:
new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.insert_at(2, 'jackfruit')
ll.print()

figs-->banana-->mango-->grapes-->orange-->
figs-->banana-->jackfruit-->mango-->grapes-->orange-->

# Let's test the code for insert_at:
new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.insert_at(0, 'jackfruit')
ll.print()

new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.insert_at(5, 'jackfruit')
ll.print()

figs-->banana-->mango-->grapes-->orange-->
jackfruit-->jackfruit-->figs-->banana-->mango-->grapes-->orange-->
figs-->banana-->mango-->grapes-->orange-->
figs-->banana-->mango-->grapes-->orange-->jackfruit-->jackfruit-->

This is same error! We forgot to use return statement

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added    

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
            return # if linked list is empty, no need to run the below code. So, return
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # if linked list is empty
        if self.head is None:
            node = Node(data, None) # create a node and point it to None because it is end
            self.head = node        # make this node as new head (because until now there is no head i.e. linked list is empty)
            return # to stop the below code from running after adding the node to an empty Linked List
        
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_end function
        for data in data_list:
            self.insert_at_end(data)
    
    def get_length(self):
        counter = 0
        # Edge case: if linked list is empty. Then we need to check the `head`
        if self.head is None:
            return 0
        # else, iterate over head
        itr = self.head
        while itr:
            itr = itr.next
            counter+=1
        return counter
    
    def insert_at(self, index: int, data: Union[str, int]):
        # Edgecases: adding element at the start, or at the end 
        if index==0:
            self.insert_at_beginning(data)
            return
        elif index == self.get_length():
            self.insert_at_end(data)
            return
        if index<0 or index>self.get_length():
            raise Exception("Out of range")
        # By now, we are adding element in a non-empty list and somewhere in the middle
        # begin from the head (i.e. start of a lInked list)
        itr = self.head
        counter = 0
        while counter<index-1:
            itr = itr.next
            counter+=1
        # above loop will break as soon as we are at node just before where we want to add the new data
        # now add new data as a node and pointing to the next node in the original linked list
        node = Node(data, itr.next)
        # now point the previous node's next pointer to the new node just added
        itr.next = node

    def remove_at(self, index: int):
        if index<0 or index>self.get_length()-1:
            raise Exception("Out of range")
        
        # Edgecases: removing element at the start, or at the end 
        if self.head is None:
            print('Cannot remove from an empty list')
            return
        # remove the first element: simply update the head
        if index==0:
            self.head = self.head.next # update the head(i.e. start) to the next node
            return # DO NOT MISS THIS
        
        # By now, we are removing element in a non-empty list and somewhere in the middle or at the end
        # begin from the head (i.e. start of a lInked list)
        itr = self.head
        counter = 0
        while counter<index-1:
            itr = itr.next
            counter+=1
        # above loop will break as soon as we are at node just before where we want to remove the data
        # now we remove the node by pointing the current node to the next's next node skipping the node at index = index
        itr.next = itr.next.next

# Let's test the code for insert_at:
new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.insert_at(0, 'jackfruit')
ll.print()

new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.insert_at(5, 'jackfruit')
ll.print()

figs-->banana-->mango-->grapes-->orange-->
jackfruit-->figs-->banana-->mango-->grapes-->orange-->
figs-->banana-->mango-->grapes-->orange-->
figs-->banana-->mango-->grapes-->orange-->jackfruit-->

# Let's test the code for remove_at:
new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.remove_at(0)
ll.print()
print('')

new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.remove_at(4)
ll.print()
print('')
new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
ll.print()
ll.remove_at(1)
ll.print()
print('')

figs-->banana-->mango-->grapes-->orange-->
banana-->mango-->grapes-->orange-->

figs-->banana-->mango-->grapes-->orange-->
figs-->banana-->mango-->grapes-->

figs-->banana-->mango-->grapes-->orange-->
figs-->mango-->grapes-->orange-->

Exercise-1: add following 2 methods:

def insert_after_value(self, data_after, data_to_insert):
    # Search for first occurance of data_after value in linked list
    # Now insert data_to_insert after data_after node

def remove_by_value(self, data):
    # Remove first node that contains data

Show solution code

class LinkedList:
    def __init__(self):
        # head is an object always pointing towards the head i.e. start of the linked list
        self.head = None # Step-1: initialize head to none. this will be updated once we add data to the linked list

    def insert_at_beginning(self, data):
        # In insert_at_beginning, we add element at the start of the linked list
        
        node = Node(data, self.head) # Steps-2&3: create a node with data and next pointer to the current head
        self.head = node             # Step-4: update the current head to the new node just added

    def print(self):        
        if self.head is None:
            print("Linked List is empty")
            return # if linked list is empty, no need to run the below code. So, return
        # to print we iterate on the node starting from the first node
        itr = self.head
        llstr = ""
        while itr:
            llstr+=str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def insert_at_end(self, data:  Union[str, int]):
        # if linked list is empty
        if self.head is None:
            node = Node(data, None) # create a node and point it to None because it is end
            self.head = node        # make this node as new head (because until now there is no head i.e. linked list is empty)
            return # to stop the below code from running after adding the node to an empty Linked List
        
        # Remember - we use head as the iterator
        itr = self.head # start from the beginning of the list
        while itr.next:
            itr = itr.next # reach the end
        # once we reach end, do 2 things:
        # 1. make the node of new data and point it to None because it is the end
        node = Node(data, None)
        # 2. update the old end's next to the new node
        itr.next = node

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_end function
        for data in data_list:
            self.insert_at_end(data)
    
    def get_length(self):
        counter = 0
        # Edge case: if linked list is empty. Then we need to check the `head`
        if self.head is None:
            return 0
        # else, iterate over head
        itr = self.head
        while itr:
            itr = itr.next
            counter+=1
        return counter
    
    def insert_at(self, index: int, data: Union[str, int]):
        # Edgecases: adding element at the start, or at the end 
        if index==0:
            self.insert_at_beginning(data)
            return
        elif index == self.get_length():
            self.insert_at_end(data)
            return
        if index<0 or index>self.get_length():
            raise Exception("Out of range")
        # By now, we are adding element in a non-empty list and somewhere in the middle
        # begin from the head (i.e. start of a lInked list)
        itr = self.head
        counter = 0
        while counter<index-1:
            itr = itr.next
            counter+=1
        # above loop will break as soon as we are at node just before where we want to add the new data
        # now add new data as a node and pointing to the next node in the original linked list
        node = Node(data, itr.next)
        # now point the previous node's next pointer to the new node just added
        itr.next = node

    def remove_at(self, index: int):
        if index<0 or index>self.get_length()-1:
            raise Exception("Out of range")
        
        # Edgecases: removing element at the start, or at the end 
        if self.head is None:
            print('Cannot remove from an empty list')
            return
        # remove the first element: simply update the head
        if index==0:
            self.head = self.head.next # update the head(i.e. start) to the next node
            return # DO NOT MISS THIS
        
        # By now, we are removing element in a non-empty list and somewhere in the middle or at the end
        # begin from the head (i.e. start of a lInked list)
        itr = self.head
        counter = 0
        while counter<index-1:
            itr = itr.next
            counter+=1
        # above loop will break as soon as we are at node just before where we want to remove the data
        # now we remove the node by pointing the current node to the next's next node skipping the node at index = index
        itr.next = itr.next.next
        
        
    def insert_after_value(self, data_after: Union[str, int], data_to_insert: Union[str, int]):
        # if linked list is empty, we cannot index the data_after, hence, raise error 
        if self.head is None:
            raise Exception("list is empty!")
        
        # else iterate over linked list, and as we find the value, we insert using insert_at
        itr = self.head # initialize the iterator at the start of the head
        counter = 0
        while itr:
            value = itr.data
            if value == data_after:
                break
            counter+=1
            itr = itr.next

        if counter==self.get_length(): # means we could not find data_after in the linked list
            raise Exception(f'data_after = {data_after} not found in the Linked List.')
        # else, insert at 1 index away from where we found data_after
        self.insert_at(counter+1, data=data_to_insert)
        
    def remove_by_value(self, data: Union[str, int]):
        # if linked list is empty, we cannot remove anything from it
        if self.head is None:
            raise Exception("list is empty!")
        
         # else iterate over linked list, and as we find the value, we remove using remove_at
        itr = self.head # initialize the iterator at the start of the head
        counter = 0
        while itr:
            value = itr.data
            if value == data:
                break
            counter+=1
            itr = itr.next

        if counter==self.get_length(): # means we could not find data to remove in the linked list
            raise Exception(f'data = {data} not found in the Linked List.')
        # else, remove the same index where we found data
        self.remove_at(counter)


##########################
# Test the code developed
##########################
new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
print('Original')
ll.print()
ll.insert_after_value('banana', 'Mousami')
print('Modified')
ll.print()
print('')
ll.insert_after_value('orange', 'Pineapple')
print('Modified-2')
ll.print()
print('')
ll.insert_after_value('Apple', 'Custard Apple')
print('Modified-3')
ll.print()
print('')
# test remove_by_value
new_data_list = ['figs','banana', 'mango', 'grapes', 'orange']
ll = LinkedList()
ll.insert_values(new_data_list)
print('Original')
ll.print()
ll.remove_by_value('mango')
print('Modified')
ll.print()
ll.remove_by_value('figs')
print('Modified-2')
ll.print()
ll.remove_by_value('mango')
print('Modified-3')
ll.print()

Exercise-2: Can you test for yourself by looking at the code above why this table is correct?

Excercise-3: Try creating a doubly Linked List by yourself.

Hint:The only difference with regular linked list is that double linked has prev node reference as well. That way you can iterate in forward and backward direction. Your node class will look this this:

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

insert_at

Show solution code

class Node:
    def __init__(self, data=None, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev
    
    
class DoublyLinkedList:
    def __init__(self):
        # initialize an empty doubly linked list. head is the start node (always)
        self.head = None # make a None start node as head
    
    def insert_at_beginning(self, data: Union[str, int]):

        # Case-1: We start with an empty Linked List
        if self.head == None:
            # make a node of the data, point next of this node to old head, point prev of this node to null/None as it is the new head (i.e. start)
            node = Node(data, next=self.head, prev=None)
            self.head = node # make the new node as the new head (i.e. start)
            return
        
        else:
            # Case-2: We have some nodes in place
            node = Node(data, next=self.head, prev=None) # make a node, point next to old head, point prev to none
            self.head.prev = node # point old head's prev to new node
            self.head = node # make the new node as the new head (i.e. start)

    
    def print_forward(self):
        if self.head is None:
            print("Linked List is empty!")
            return
        
        # else we will print it. 
        # Iterate over the head, starting from the first node and moving 1 step further.
        itr = self.head
        llstr = ""
        while itr:
            llstr+= str(itr.data)
            llstr+='-->'
            itr = itr.next
        print(llstr)

    def get_last_node(self):
        if self.head is None:
            print("Linked List is empty!")
            return
        # else, iterate and get the last node
        itr=self.head
        while itr.next: # NOT itr. Can you reason-Why?🤔
            itr = itr.next
        return itr


    def print_backward(self):
        if self.head is None:
            print("Linked List is empty!")
            return
        # else we will print it. 
        # Iterate over the head, starting from the first node and moving 1 step further.
        itr = self.get_last_node()
        llstr = ""
        while itr:
            llstr+= str(itr.data)
            llstr+='-->'
            itr = itr.prev
        print(llstr)

    def insert_at_end(self, data: Union[str, int]):

        # Case-1: We start with an empty Linked List
        if self.head == None:
            # make a node of the data, point next of this node to old head, point prev of this node to null/None as it is the new head (i.e. start)
            node = Node(data, next=self.head, prev=None)
            self.head = node # make the new node as the new head (i.e. start)
            return
        
        else:
            # Case-2: We have some nodes in place
            last_node = self.get_last_node() # get the last node
            node = Node(data, next=None, prev=last_node) # make a node, point next to None, point prev to last node in linked_list
            last_node.next = node # point last node's next to new node

    def get_length(self):
        counter = 0
        # Edge case: if linked list is empty. Then we need to check the `head`
        if self.head is None:
            return 0
        # else, iterate over head
        itr = self.head
        while itr:
            itr = itr.next
            counter+=1
        return counter
            

    def insert_at(self, index: int, data: Union[str, int]):
        # Edgecases: adding element at the start, or at the end 
        if index==0:
            self.insert_at_beginning(data)
            return
        elif index == self.get_length():
            self.insert_at_end(data)
            return
        if index<0 or index>self.get_length():
            raise Exception(f"index= {index} is Out of Range!")
        # By now, we are adding element in a non-empty list and somewhere in the middle
        # begin from the head (i.e. start of a doubly linked list)
        itr = self.head
        counter = 0
        while counter<index-1:
            itr = itr.next
            counter+=1
        # above loop will break as soon as we are at node just before where we want to add the new data
        
        node = Node(data, next=itr.next, prev=itr)# Create node of new data; point it's next to the next node in the original linked list; point it's prev to current itr node
        if node.next:
            node.next.prev = node # if next node exists, point its prev to new node
        itr.next = node # point previous node's next pointer to the new node just added

    def insert_values(self, data_list: List):
        # initialize a new linked list
        self.head = None

        # Use the insert_at_end function
        for data in data_list:
            self.insert_at_end(data)


##########################
# Test the code developed
##########################
dll = DoublyLinkedList()
dll.print_forward()
dll.print_backward()
# insert_at_beginning
dll.insert_at_beginning('apple')
dll.insert_at_beginning('banana')
dll.insert_at_beginning('mango')
dll.print_forward()
dll.print_backward()
# insert_at_end
dll.insert_at_end('grapes')
dll.print_forward()
# insert_at
dll.insert_at(1, 'mausami')
dll.print_forward()
dll.insert_at(0, '0')
dll.print_forward()
dll.insert_at(6, '6')
dll.print_forward()
# insert_values
dll = DoublyLinkedList()
fruits_list = ['apple', 'banana']
dll.insert_values(fruits_list)
dll.print_forward()

Resources:

Codebasics Lecture on Linked List