Linked List in Python

Posted in PYTHON

Linked List in Python
vinaykhatri

Vinay Khatri
Last updated on February 11, 2025

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.

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.

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:

Vinay

Vinay Khatri
I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Related Blogs

Best way to convert string to bytes in Python 3
PYTHON

Best way to convert string to bytes in Python 3

In this tutorial, we will learn how to convert a String to a Byte in Python and vice versa. After r…

11 February, 2025
How to Check if a Python String Contains a Substring
PYTHON

How to Check if a Python String Contains a Substring

Unfortunately, Python does not have any specific contains or substring method to check if a string …

10 February, 2025
Top 10 Real-World Python Applications That You Should Know
PYTHON

Top 10 Real-World Python Applications That You Should Know

We live in a world where people and businesses rely highly on software applications to accomplish v…

10 February, 2025

Leave a Comment on this Post

0 Comments