How to construct a Linked List with print, append, insert, pop, and remove functionality in Python?

Pre-requisites: You should be knowing python and basics of class and object

A linked List is nothing but just a piece of information stored in the memory and all the information (data) are connected (linked) to each other in the form of a chain. Here we will be learning how to create that chain and construct a Linked List.

One of the standout features of Linked Lists is their ability to efficiently insert and remove elements, making them a valuable choice for scenarios where data is frequently modified.

Source: GFG

Why Linked List?

There are multiple advantages of a Linked list. I’ve given only two most important reasons to use a Linked List.

1. A linked list is dynamic in nature and uses memory more efficiently than an array because a linked list stores the only data that is being used in the runtime.
2. A linked list allows efficient insertion/deletion whereas an array requires O(N) complexity.

Implementing Linked List in Python

Creating Node:

A Node is an object that holds two pieces of information about the data.
The value and the reference to the next value. By default, the reference will be null.

class Node:
    def __init__(self, value):  # Excepts one parameter, the value 
        self.value = value      # Attribute (Variable) that stores the value
        self.next = None        # Another attribute that will store the reference of next node

Believe me or not, that’s the entire structure of the linked list.

Creating links between Nodes

Now let’s see how we can add data and create links in between.

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

#Creating Nodes
a = Node("A")
b = Node("B")
c = Node("C")
#A, B & C are the data here

#Now lets build the links like a -> b -> c
a.next = b
b.next = c

As I told above the self.next will use a reference to the next node that's why I used a.next and b.next.

Printing value of Nodes of Linked List

Now again you have to believe me that we have successfully created a link between a, b and c, just we are not able to see it as of now.

So let’s write the code so that we can see links.

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

#Creating Nodes
a = Node("A")
b = Node("B")
c = Node("C")

#Now lets build the links like a -> b -> c
a.next = b
b.next = c

#Create stating point of the list (head)
head = a    #a is the stating point of linked list
while head:
    print(head.value, end = "->")
    head = head.next

#Output
# A->B->C

So I have stored the starting point of the Linked List in the head variable. The head is updating itself to its next pointer in each iteration and will be null after printing C, because c.next is null, this is where I can stop the iteration and this is what the while loop is doing. While there is some value in the head it will continue running and the moment the head becomes None, the loop will get stopped.

Append, Insert and Delete Operations

Append Function

So far we created the links manually, let's write the code for appending a node in the Linked List. For this, we will create another class called LinkedList that will contain a function for printing node ( print( ) ) and another function that will add a given node ( append( ) )at the end of the linked list.

Please read the comment to understand what each line is doing.

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

#Linked List Class that will have all functionality
class LinkedList:
    def __init__(self):
        self.head = None
    
    #Function for appending value at the end of the list
    def append(self, value):
        cur_node = Node(value)  # Creating node out of given value
        cur_head = self.head    # Store ref of head in a variable

        # If there is no node then head will be None, in this case  
        # cur_node will become the head of the linked list and come
        # out of function

        if not cur_head:        
            self.head = cur_node
            return
        # When the next node of the cur_head is None,
        # it meanse cur_head.next should be my cur_node
        # So will break the loop here and make 
        # cur_head.next = cur_node
        
        while cur_head.next:
            cur_head = cur_head.next
        cur_head.next = cur_node

    #Function for printing values
    def print(self):
        temp_head = self.head
        while temp_head:
            print(temp_head.value, end = '->')
            temp_head = temp_head.next   

Appending a new node at the end of the linked list

Well, you might be thinking 🤔 why we are storing ref of self.head in another variable, why not use that directly?

So, always remember to never use self.head directly, until it is required. Always use references. It is like a key to your home, if you take it, no one else in your family will have access to your home. So always use a copy (ref) of your key so others in your family can have access to the other copy of the key.

Similarly, there are multiple functions (members) in your class (family), if one function changes the head position, so other will have the wrong head reference.

Now let’s add other functionality

Insert Function

Now let’s create a function that allows us to add a value at the desired location/position. Please read the comment to understand what each line is doing.

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

#Linked List Class that will have all functionality
class LinkedList:
    def __init__(self):
        self.head = None
    
    #Function for appending value at the end of the list
    ....

    #Function for printing values
    ....

    #Function for inserting value a the given position (if exist)
    def insert(self, position, value):

        # Store head reference and create node out of given vale
        cur_node, cur_head = Node(value), self.head
        
        # First if the position is 0
        if position == 0:
            cur_node.next = self.head
            self.head = cur_node
        
        # Else now will go just before the position where we want to insert
        # the value so that we make the cur_head.next = cur_node
        for i in range(position - 1):

            # Within the given position if we get next ref as none, then
            # we can not insert the value
            if not cur_head.next:
                print("Index Out of range")
                return
            cur_head = cur_head.next
        
        # Once we reached just before the desired location
        # Now we can say cur_head.next = cur_node
        cur_head.next = cur_node
        
        # Now next value of cur_node will be next of next of cur_head
        cur_node.next = cur_head.next.next

If the position is 0 the cur_node.next will be self.head and now head will switch to cur_node.

Source: GFG

Deleting Node

Now let's see how we can delete a node from a linked list. There are two ways to delete a node.

1. Using the index, the pop( ) function.
2. Using value name, the remove( ) function

pop( ) function

Deleting a value is going to be a simple loop to skip the given index. But additionally, we have to check for an empty linked list and index 0.

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

#Linked List Class that will have all functionality
class LinkedList:
    def __init__(self):
        self.head = None
    
    #Function for appending value at the end of the list
    ....

    #Function for printing values
    ....

    #Function for inserting value a the given position (if exist)
    ...

    #Function for deleting value of given index
    def pop(self, index):
        #Get the corrent head
        cur_head = self.head

        # if list is empty
        if not cur_head:
            print("List is empty")
            return
        
        #Handle index = 0
        if index == 0:
            # Switch the head to its next pointer
            self.head = self.head.next
            return

        #Loop that will take me just before the node that I want to delete
        for i in range(index - 1 ):
            cur_head = cur_head.next
        cur_head.next = cur_head.next.next

remove( ) function

This function will ask for the value that the user wants to delete. Will iterate over the linked list and try to find the value in the cur_head.next, then change the next reference to cur_head.next.next.

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

#Linked List Class that will have all functionality
class LinkedList:
    def __init__(self):
        self.head = None
    
    #Function for appending value at the end of the list
    ....

    #Function for printing values
    ....

    #Function for inserting value a the given position (if exist)
    ...

    #Function for deleting value of given index
    ...

    #Function for deleting the given value
    def remove(self, value):
        # Get the head
        cur_head = self.head

        #If head the value
        if cur_head.value == value:
            self.head = self.head.next
            return

        #Else will iterate till find the value
        while cur_head.next:
            if cur_head.next.value == value:
                cur_head.next = cur_head.next.next
                return
            cur_head = cur_head.next

Conclusion

In this article, we’ve explored the fundamental operations of a Linked List data structure, including print(), insert(), append(), pop(), and remove(). We've seen how Linked Lists offer a flexible way to manage data, especially when it comes to dynamic data structures.