Linked List in Python

Posted in /  

Linked List in Python

Vinay Khatri
Last updated on June 10, 2022

    A linked list is one of the basic data structures present in computer science. To represent a linked list we create a sequence of nodes or a chain of nodes. In the sequence of nodes, the first node is called the head of the Linked List and the last node is known as the tail. In the linked list every node has a pointer to the next node, which means each node contains a piece of extra information next representing the next node connected to it. [caption id="attachment_22113" align="aligncenter" width="616"] Singly Linked List[/caption] The above image is an example of a singly linked list, where each node is pointing to its next node, except for the Tail node. Apart from a singly linked list, there is also a data structure which is known as a doubly-linked list. [caption id="attachment_22115" align="aligncenter" width="528"] Doubly Linked List[/caption] In this doubly linked list, each node contains two pointers, one pointer to the next node and one pointer to the previous node. There are many cases where we use the linked list to solve real-world problems. Linked lists provide an alternative to the standard list or arrays present in Python.

    • Linked list allow us to add and remove elements with linear time complexity.
    • Managing items in a linked list are also very easy.
    • In linked list insertion item in the middle of the list is cheap as compared to the list and array data structure.

    Note: The linked list is an alternative to the static arrays, whereas in Python the list data structure is more a dynamic data structure, which is as efficient as a linked list. In this tutorial, we will learn the concept of the Linked List data structure and learn how to implement a custom Linked List in Python using class and objects.

    Singly Linked List

    A singly linked list is a sequential data structure, made of nodes. A node is a single block in the linked list structure that contains some data. We can also define a linked list as a sequential chain of nodes. Where the first node is known as the Head and the last node Tail .  In the singly linked list, each node contains a pointer to the next node, which connects one node to the next node in the linked list. Only the tail node does not point to any next node.

    How to implement a singly linked list in Python?

    Here are the steps to define or implement a singly linked list in Python

    Step 1: Create a Node class

    For the singly linked list, the node class can contain any type of data, but it must have a next pointer that can point to the next node. The initial value of the next node should be None because it is always expected to be the last node in the linked list.

    #Node Class
    class Node:
    
        def __init__(self, data):
            #node data
            self.data = data
    
            #pointer to the next node
            self.next = None

    The Node class can accept a data argument.

    Step 2: Create a linked list class that will manage nodes by adding, deleting, and traversing through the nodes.

    Whenever we create a linked list, it should have two information when initializing its object, the head node, and tail node information. But when we define a linked list, without any nodes in it the value of Head and Tail would be None .

    class LinkedList:
    
        def __init__(self):
    
            #head pointing to the head node or the first node
            self.head = None
    
            #tail will point to the tail node or the last node
            self.tail = None
    
            #the total length of the LinkedList
            self.length = 0

    The self.length property is just for some extra information about the linked list. The self.length property defines the total length of the linkedlist.

    Step 3: Define the methods in the LinkedList that will add a node at the end, insert a node in between, delete a node from the LinkedList and traverse node in the linked list.

    Let’s start with the method that will add the node to the linked list. Add Node in the Linked List.

    # add node in the linked list(at the end)
    
        def append(self, data):
            #if there is no node in the linked list
            #create a node
            #for the first node
            #the head and the tail would point to the same node
            if not self.head:
                new_node = Node(data)   #create a node
                self.head = new_node
                self.tail = new_node
                self.length += 1   #increase the length of linked list by 1
    
            #if is a node in the linked list
            #create a new node
            #point the current tail node pointer  to the new node
            #set the new node as the tail node
            else:
                new_node = Node(data)
                self.tail.next = new_node  
                self.tail = new_node
                self.length += 1   #increase the length of the linked list by 1

    In the above example, we have defined the append method in the LinkedList class to add a new node to the Linked List.   In the first, if condition if not self.head: the statement is checking if the LinkedList already has some node or it's empty. If the LinkedList is empty then the value of self.head and self.tail would be None. And the node that is added to the linked list would be the first node and it will be the head and tail node for the LinkedList. In the else statement, the code is instructing that if the LinkedList already has one or more than one node, then create the new node, point the current tail node next pointer to the new node(because it is adding at the last), and set the value of tail to the new node because the LinkedList now have a new tail node. Insert a Node in the Linked List In the above section, we see how can we add a node at the end of the Linked List, now let’s write insert(pos, data) , that can insert the new node in between the linked list.

    #insert the new node in the between of the linked list
        def insert(self, pos, data):
            #insert the new node at the end of the list
            #if the position is greater than the total length of the list
            if pos>self.length:
                self.append(data)
    
            #if the pos is 1
            # the new head
            elif pos == 1:
                new_node = Node(data)
                new_node.next = self.head
                self.head = new_node
                self.length += 1      #increase value of length
    
            #if the pos in between the linked list
            else:
    
                temp = self.head
    
                #traverse to the position-1
                #where we want to insert the new node
                for i in range(1, pos-1):
                    temp= temp.next
    
                #create a new node
                new_node = Node(data)
    
                #get the pointer that is pointing to the current node
                #which is located at position pos
                current = temp.next
    
                #set the position-1 node next node to the newly created node
                temp.next = new_node
    
                #set the newly created next node value to the old node
                new_node.next = current
    
                self.length += 1   #increase the value of length

    Delete a Node in the Linked List To delete a node from the linked list, we will point the previous node of the Node to the next node of the node.

    #the delete method to delete the node from the linked list
        def delete(self, pos):
            temp = self.head
    
            #traverse to the position
            #track the previous node
            #track the current node with temp that you want to delete
            for i in range(1, pos):
                prev = temp
                temp= temp.next
    
            #if the node that to delete is the head node
            if temp== self.head:
                self.head = temp.next
    
            #if the node that to delete is the tail node
            elif temp==self.tail:
                self.tail= prev
    
            #if the node that to delete is between the linked list
            else:
                prev.next= temp.next
    
            self.length -= 1   #decrease the length of the linkedlist by 1

    Traverse through the linked list To traverse through the linked list means to go through every linked list node and display them.

        #display all the node data sequentially from head to tail
        def traverse(self):
            print("Head--->", end=" ")
            temp = self.head
    
            while temp:
                print(temp.data, end=" ")
                temp= temp.next
    
            print("<----Tail")

    Python program to implement singly list

    Put all the code together and run

    #Node Class
    class Node:
    
        def __init__(self, data):
            #node data
            self.data = data
    
            #pointer to the next node
            self.next = None
    
    class LinkedList:
        def __init__(self):
            #head pointing to the head node or the first node
            self.head = None
    
            #tail will point to the tail node or the last node
            self.tail = None
    
            #the total length of the LinkedList
            self.length = 0
    
        # add node in the linked list(at the end)
        def append(self, data):
    
            #if there is no node in the linked list
            #create a node
            #for the first node
            #the head and the tail would point to the same node
            if not self.head:
                new_node = Node(data)   #create a node
                self.head = new_node
                self.tail = new_node
                self.length += 1        #increase the length of linked list by 1
    
            #if is a node in the linked list
            #create a new node
            #point the current tail node pointer  to the new node
            #set the new node as the tail node
            else:
                new_node = Node(data)
                self.tail.next = new_node  
                self.tail = new_node
                self.length += 1        #increase the length of the linked list by 1
    
        #insert the new node in the between of the linked list
        def insert(self, pos, data):
            #insert the new node at the end of the list
            #if the position is greater than the total length of the list
            if pos>self.length:
                self.append(data)
    
            #if the pos is 1
            # the new head
            elif pos == 1:
                new_node = Node(data)
                new_node.next = self.head
                self.head = new_node
                self.length += 1      #increase value of length
            #if the pos in between the linked list
            else:
                temp = self.head
                #traverse to the position-1
                #where we want to insert the new node
                for i in range(1, pos-1):
                    temp= temp.next
    
                #create a new node
                new_node = Node(data)
                #get the pointer that is pointing to the current node
                #which is located at position pos
                current = temp.next
    
                #set the position-1 node next node to the newly created node
                temp.next = new_node
    
                #set the newly created next node value to the old node
                new_node.next = current
    
                self.length += 1   #increase the value of length
    
        #the delete method to delete the node from the linked list
        def delete(self, pos):
            temp = self.head
    
            #traverse to the position
            #track the previous node
            #track the current node with temp that you want to delete
            for i in range(1, pos):
                prev = temp
                temp= temp.next
    
            #if the node that to delete is the head node
            if temp== self.head:
                self.head = temp.next
    
            #if the node that to delete is the tail node
            elif temp==self.tail:
                self.tail= prev
    
            #if the node that to delete is between the linked list
            else:
                prev.next= temp.next
            self.length -= 1   #decrease the length of the linkedlist by 1
    
        #display all the node data sequentially from head to tail
        def traverse(self):
    
            print("Head--->", end=" ")
    
            temp = self.head
    
            while temp:
                print(temp.data, end=" ")
                temp= temp.next
           
            print("<----Tail")
    
    l = LinkedList()
    
    l.append('a')   #a
    l.append('b')   # a b
    l.append('c')   # a b c
    l.insert(2, 20)  # a 20 b c
    l.append('d')   #a 20 b c d
    l.delete(2)    # a b c d
    l.insert(100, 'e') # a b c d e
    l.traverse()

    Output

    Head---> a b c d e <----Tail

    Doubly Linked List

    The doubly linked list is similar to the singly linked list, the only difference is, the doubly linked list node contains two pointers prev and the next . The prev pointer points to the previous node and the next pointer points to the next node in the linked list. In the case of a doubly-linked list the head node’s prev points to None and the next points to the next node and the tail node’s prev points to the second last node, and the next points to None.

    Doubly Linked list Implementation in Python

    Step 1: Create a Node class

    Both singly and doubly linked lists are a sequential chain of nodes. And similar to the singly linked list we have to create a Node class for the doubly linked list.

    #Node Class for doubly linked list
    
    class Node:
    
        def __init__(self, data):
            #node data
            self.data = data
    
            #pointer to the next node
            self.next = None
    
            #pointer to the previous node
            self.prev = None

    The node of the doubly linked list contains two pointers self.next and self.prev, that points to the next and previous node.

    Step 2: Define the linked list class

    After defining the Node class let’s define the LinkedList class for the doubly linked list, which will contain methods and properties to manage the linked list.

    class LinkedList:
    
        def __init__(self):
            #head pointing to the head node or the first node
            self.head = None
    
            #tail will point to the tail node or the last node
            self.tail = None
    
            #the total length of the LinkedList
            self.length = 0

    Step 3: Define the operations of a doubly-linked list as LinkedList Methods

    Let’s start with append method that will add the node at the end of the linked list.

    def append(self, data):
            #if there is no node in the linked list
            if not self.head:
                #create a new node
                new_node = Node(data)
                #set the head and tail to the new node
                self.head = new_node
                self.tail = new_node
    
            #if there is one or more than one node in the linked list
            else:
                #create a new node
                new_node = Node(data)
    
                #set the new node to the next of the current tail node
                self.tail.next = new_node
    
                #set the current tail node as previous node of the new node
                new_node.prev = self.tail
    
                #set the new node as the tail node
                self.tail = new_node
    
            self.length+=1    #increase the length of the linked list by 1

    In the append method, we set 2 conditions in the.

    1. The first condition is set for the linked list if there is no node in the linked list.
    2. And the second condition is set if there is one or more than one node in the linked list. And we want to add the new node at the end of the list.

    Insert Method In the insert method, we will define the insert new node in the doubly linked list. To insert a new node we need set select a position where the node is needed to insert.

    #method to insert new node at a specific position pos
        def insert(self, pos, data):
    
            #if to insert the new node at the head.
            if pos ==1:
                new_node = Node(data)
                new_node.next= self.head
                self.head.prev = new_node
                self.head = new_node
    
            #to insert the new node at the end of the linked list
            elif pos>self.length:
                self.append(data)
    
            #To insert the new node between the linked list
            else:
                temp = self.head
    
                #go to the position of the nodes
                for i in range(1, pos):
                    temp = temp.next
    
                #create a new node
                new_node = Node(data)
    
                #set the new node next and prev pointers
                new_node.next = temp
    
                new_node.prev = temp.prev
    
                #point the previous node next to the new node
                temp.prev.next = new_node
    
                #set the next node previous pointer to the new node
                temp.prev = new_node
    
            self.length +=1  #increase the length of the linked list by 1

    Delete Method We can also delete the node from a doubly linked list. To delete a node we just need to manipulate the targeted node's previous and next nodes.

    #method to delete node from the specific position pos
        def delete(self, pos):
            #to delete the head node
            if pos==1:
                self.head = self.head.next
                self.head.prev = None
    
            #to delete the tail node
            elif pos >= self.length:
                self.tail = self.tail.prev
                self.tail.next = None
    
            #to delete the node in betweeen the linked list
            else:
                temp= self.head
    
                for i in range(1, pos):
                    temp= temp.next
    
                temp.prev.next = temp.next
                temp.next.prev= temp.prev
    
            self.length-=1   #decrease the length of the linked list by 1

    Traverse method

    As the Doubly linked list has two pointers next and prev, we can traverse a doubly linked list from head to tail and tail to head.

        #display all the node data sequentially from head to tail
        def traverse(self):
            print("Head--->", end=" ")
            temp = self.head
    
            while temp:
                print(temp.data, end=" ")
                temp= temp.next
           
            print("<----Tail")
    
        #display all the node data sequentially from tail to head
        def trackback(self):
            print("Tail--->", end=" ")
            temp = self.tail
    
            while temp:
                print(temp.data, end=" ")
                temp= temp.prev
           
            print("<----Head")

    Python Doubly linked list program with append, insert, delete and traverse methods

    Now put all the code together and execute.

    #Node Class for doubly linked list
    class Node:
        def __init__(self, data):
            #node data
            self.data = data
    
            #pointer to the next node
            self.next = None
    
            #pointer to the previous node
            self.prev = None
    
    class LinkedList:
        def __init__(self):
            #head pointing to the head node or the first node
            self.head = None
    
            #tail will point to the tail node or the last node
            self.tail = None
    
            #the total length of the LinkedList
            self.length = 0
    
        def append(self, data):
            #if there is no node in the linked list
            if not self.head:
                #create a new node
                new_node = Node(data)
                #set the head and tail to the new node
                self.head = new_node
                self.tail = new_node
    
            #if there is one or more than one node in the linked list
            else:
                #create a new node
                new_node = Node(data)
    
                #set the new node to the next of the current tail node
                self.tail.next = new_node
                #set the current tail node as previous node of the new node
                new_node.prev = self.tail
                #set the new node as the tail node
                self.tail = new_node
           
            self.length+=1    #increase the length of the linked list by 1
    
        #method to insert new node at a specific position pos
        def insert(self, pos, data):
            #if to insert the new node at the head.
            if pos ==1:
                new_node = Node(data)
                new_node.next= self.head
                self.head.prev = new_node
                self.head = new_node
    
            #to insert the new node at the end of the linked list
            elif pos>self.length:
                self.append(data)
    
            #To insert the new node between the linked list
            else:
                temp = self.head
                #go to the position of the nodes
                for i in range(1, pos):
                    temp = temp.next
    
                #create a new node
                new_node = Node(data)
    
                #set the new node next and prev pointers
                new_node.next = temp
                new_node.prev = temp.prev
    
                #point the previous node next to the new node
                temp.prev.next = new_node
                #set the next node previous pointer to the new node
                temp.prev = new_node
    
            self.length +=1  #increase the length of the linked list by 1
               
        #method to delete node from the specific position pos
        def delete(self, pos):
            #to delete the head node
            if pos==1:
                self.head = self.head.next
                self.head.prev = None
    
            #to delete the tail node
            elif pos >= self.length:
                self.tail = self.tail.prev
                self.tail.next = None
    
            #to delete the node in betweeen the linked list
            else:
                temp= self.head
    
                for i in range(1, pos):
                    temp= temp.next
    
                temp.prev.next = temp.next
                temp.next.prev= temp.prev
           
            self.length-=1   #decrease the length of the linked list by 1
    
        #display all the node data sequentially from head to tail
        def traverse(self):
            print("Head--->", end=" ")
            temp = self.head
            while temp:
                print(temp.data, end=" ")
                temp= temp.next
           
            print("<----Tail")
    
        #display all the node data sequentially from tail to head
        def trackback(self):
            print("Tail--->", end=" ")
            temp = self.tail
    
            while temp:
                print(temp.data, end=" ")
                temp= temp.prev
    
            print("<----Head")
    
    l = LinkedList()
    
    l.append('a')       #a
    l.append('b')       # a b
    l.append('c')       # a b c
    l.append('d')       #a b c d
    l.insert(45, 'e')   #a  b c d e
    l.insert(1, 'Z')    #Z a b c d e
    l.insert(4, 'D')    # Z a b c D d e
    l.delete(4)         # Z a b c d e
    l.append('f')       # Z a b c d e f
    l.delete(6)         # Z a b c d f
    
    l.traverse()
    print("\n\n")
    l.trackback()

    Output

    Head---> Z a b c d f <----Tail
    
    Tail---> f d c b a Z <----Head

    Conclusion

    In this Python tutorial, we learned what is singly and doubly linked list in Python and how to implement them. In a singly linked list, every node has a next pointer variable that points to the next node, which makes the singly linked list a unidirectional sequential data structure. On the other hand, the doubly linked list’s nodes have two pointer variables next and prev( previous), which point to the next and previous nodes.

    People are also reading:

    Leave a Comment on this Post

    0 Comments