An Introduction to Python Linked List and How to Create One

A Python linked list is an abstract data type that presents a linear collection of data organized as nodes that then link to another node. Build your own with this guide. 

Written by Philip Wilkinson
Published on Sep. 30, 2022
An Introduction to Python Linked List and How to Create One
Image: Shutterstock / Built In
Brand Studio Logo

A linked list is an abstract data type that acts as a linear collection of data elements organized as a collection of nodes that contains information about what that node contains and then a link to another node. This can take two main forms: It can be a singly linked list, which has only one direction of links between nodes, or a doubly-linked list, which can be linked to both the next and last item in the list. The benefit of this over a regular array or list is that elements can be easily inserted and removed without changing the index of all other items. The memory used to store the linked list also doesn’t need to be reorganized because the data doesn’t have to be stored contiguously. However, you can’t access items in constant time (O(1)) like you can with an array because looking up an item in the list has a linear time complexity (O(n)).

What Is a Python Linked List?

A Python linked list is an abstract data type in Python that allows users to organize information in nodes, which then link to another node in the list. This makes it easier to insert and remove information without changing the index of other items in the list.  

This data structure can be useful when:

  • You want to insert items easily in between other items.
  • The size of the total collection is unknown.
  • You don’t need random access when searching for items.
  • There is no concern about memory usage for storing the data.

More on Python Lists From Built In ExpertsHow to Append Lists in Python

 

How to Create a Linked List in Python

With this in mind, we can then begin to think about how to implement linked lists in an actual data structure in Python. Key methods commonly associated with this include:

  • insert(): Add an item to the linked list at the head of the list.
  • find(): Find an item within the linked list.
  • remove(): Remove a given item with a given value.
  • is_empty(): Returns whether the linked list is empty or not.
  • get_count(): Returns the number of items in the linked list.

What’s interesting is that there is no natural data structure within Python that we can build on to construct this linked list. For a queue and a stack, we’re able to utilize the list data structure already built into Python. But before we can implement a linked list, we need to construct a node class.

This is because each item within the linked list is itself a separate object that can contain any information that it wants, along with identifying the next item in the linked list. It must have an attribute that points to, or identifies, the information that it contains, as well as an attribute that points to the next node in the linked list. For this, we must also add behaviors that allow us to both extract the data that this node contains and the next node, along with the ability to set or adjust these attributes. As such, this can be implemented as:

Class Node(object):

    def __init__(self, val):
        self.val = val
        self.next = None

    def get_data(self):
        return self.val

    def set_data(self, val):
        self.val = val
 
    def get_next(self):
        return self.next
 
    def set_next(self, next):
        self.next = next

We have val and next attributes that correspond to the data that the node holds, while also pointing to the next node in the linked list. The fact that we originally set next to None shows that we create one in the beginning with no given next node. We then also add methods that allow us to both print out the current val and next node, along with the ability to change the val and set the next node as well.

With this in mind we can then create the linked list. We will be focusing on a singly linked list which means that each node only has a link to the next in the linked list, as we can see in the node implementation above.

More on PythonIncrease the Readability of Your Python Script With 1 Simple Tool

 

How to Build a Singly Linked List in Python

The first step is to create the constructor, which will be called whenever a linked list is created. In this instance, we start with two attributes:

  • Head: The first node in the linked list.
  • Count: The number of nodes in the linked list.

We’ll first create an empty head so that we start with an empty linked list. This also means we don’t have to check whether we have a head when we first add an item. We also add a count attribute so that when adding or removing items, we can add or minus one from this. This means that when we want to check how many items we have in the linked list, we can simply call this attribute rather than loop over the entire list. This creates a tradeoff by adding complexity to adding and removing functions, while removing time complexity when trying to find the length.

This can be implemented as follows:

Class LinkedList(object):

    def __init__(self, head = None):
        self.head = head
        self.count = 0

 

How to Add Items to a Linked List in Python

With the linked list, it’s important to be able to add items, or nodes, to the list itself. For now, we will focus only on adding items to the head of the linked list. However, this can be extended to adding items anywhere in the list depending on whether this is by index or by being before or after another item. The way in which we do this at the head is simple and makes for a good starting point.

We start by instantiating a new node, assigning the data to the new node, setting the next of the new node to the current head of the list, and then setting the head of the linked list to the new node. This makes the process nice and easy with low time complexity, compared to doing the same thing to a standard list in Python. This can be implemented as follows:

    def insert(self, data):
        """
        Create a new node at the Head of the Linked List

        This has a time complexity of O(1) as we are simply changing
        the current head of the Linked List and no indices have to   
        change
        """ 

        #create a new node to hold the data
        new_node = Node(data)
        
        #set the next of the new node to the current head
        new_node.set_next(self.head)

        #set the head of the Linked List to the new head
        self.head = new_node

        #add 1 to the count
        self.count += 1

Now that we can add items to our linked list, the next thing we’ll want to do is search that linked list to see what data is part of the linked list. There are multiple ways of doing this, including searching by value or by index. We will focus on searching by value for simplicity sake.

To do this, we can  iterate over the linked list to see whether any node’s data matches the value for which we are searching. This means that in a worst-case scenario, we have to iterate over all items within the linked list. So, the time complexity takes on O(n). When we find the item, we can then return that node. Or in the case that that value does not exist, then we can return None to avoid any errors being thrown.

    def find(self, val):
        """
        Search for item in Linked List with data = val
        
        Time complexity is O(n) as in worst case scenario
        have to iterate over whole Linked List
        """

        #start with the first item in the Linked List
        item = self.head

        #then iterate over the next nodes
        #but if item = None then end search
        while item != None:
           
           #if the data in item matched val
           #then return item
           if item.get_data() == val:
               return item
           
           #otherwise we get the next item in the list
           else:
                item = item.get_next()

        #if while loop breaks with None then nothing found
        #so we return None
        return None

 

How to Remove Items From a Python Linked List

If we can find items, what about deleting them from the linked list? We don’t only want to be able to add and find items, we also want to be able to remove items in the linked list. This is another function that could be constructed in different ways, but in this case, we’ll focus on removing items that have a certain value rather than by index. This then follows a similar logic to the find function above.

The main difference between removing an item from a linked list and a regular list is that in the linked list, the node can still exist somewhere. We just change the pointer from the previous node from that node to the next node. This makes removing items from the linked  list relatively easy compared to a regular list, since not all items after the removed node have to have their index changed. Only the connection between nodes needs to be changed. This can be implemented as follows:

    def remove(self, item):
        """
        Remove Node with value equal to item

        Time complexity is O(n) as in the worst case we have to 
        iterate over the whole linked list
        """

        #set the current node starting with the head
        current = self.head
        #create a previous node to hold the one before
        #the node we want to remove
        previous = None

        #while current is note None then we can search for it
        while current is not None:

            #if current equals to item then we can break
            if current.data == item:
                break

            #otherwise we set previous to current and 
            #current to the next item in list
            previous = current
            current = current.get_next()

        #if the current is None then item, not in the list
        if current is None:
            raise ValueError(f"{item} is not in the list")
        #if previous None then the item is at the head
        if previous is None:
            self.head = current.next
            self.count -= 1

        #otherwise then we remove that node from the list
        else:
             previous.set_next(current.get_next())
             self.count -= 1

 

Python Linked List Functions to Know

With the main functionality of a linked list created, we can start adding other methods that would make using the linked list simpler. Two supplementary methods that we can add include getting the length of the linked list and seeing if the list is empty.

More on PythonHow to Write Nested List Comprehensions in Python

 

Finding the Length of a Linked List

The first method of returning the length of the linked is relatively easy. This is because of the way in which we have implemented the constructor method, along with the insert and remove methods. In doing so, we created the count attribute, which goes up whenever we insert new nodes to the linked list and goes down whenever we take away nodes using the remove method. Thus, we can return the value stored in the count attribute as follows:

    def get_count(self):
        """
        Return the length of the Linked List

        Time complexity O(1) as only returning a single value
        """

        return self.count

 

Determining Whether a Python Linked List Is Empty or Not

What about seeing if the linked list is empty? We can do this in a similar way to getting the count attribute and checking whether it’s zero or not. For simplicity’s sake, we can easily check whether the linked list is empty by seeing whether or not the head attribute is empty or not. If for some reason the count attribute was not implemented properly, we can easily check whether the head is empty, as that would indicate that we have no nodes at all.

    def is_empty(self):
        """
        Returns whether the Linked List is empty or not

        Time complexity O(1) as only returns True or False
        """

        #we only have to check the head if is None or not
        return self.head == None
An introduction to Python linked lists. | Video: Brian Faure

 

Putting the Python Linked List Together

Thus, we have implemented the main functionality of a singly linked list in Python. All that remains is to put this all together, which can be done as follows:

Class Node(object):
  
    def __init__(self, val):
        self.val = val
        self.next = None
        
    def get_data(self):
        return self.val
      
    def set_data(self, val):
        self.val = val
 
    def get_next(self):
        return self.next
 
    def set_next(self, next):
        self.next = next
      
 
Class LinkedList(object):
  
    def __init__(self, head = None):
        self.head = head
        self.count = 0
        
    def insert(self, data):
        """
        Create a new node at the Head of the Linked List
        """ 
        #create a new node to hold the data
        new_node = Node(data)
        
        #set the next of the new node to the current head
        new_node.set_next(self.head)
        
        #set the head of the Linked List to the new head
        self.head = new_node
        
        #add 1 to the count
        self.count += 1
        
    def find(self, val):
        """
        Search for item in Linked List with data = val
        
        Time complexity is O(n) as in worst case scenario
        have to iterate over whole Linked List
        """
        #start with the first item in the Linked List
        item = self.head
        #then iterate over the next nodes
        #but if item = None then end search
        while item != None:
           
           #if the data in item matched val
           #then return item
           if item.get_data() == val:
               return item
           
           #otherwise we get the next item in the list
           else:
                item = item.get_next()
              
        #if while loop breaks with None then nothing found
        #so we return None
        return None
  
    def remove(self, item):
        """
        Remove Node with value equal to item
        Time complexity is O(n) as in the worst case we have to 
        iterate over the whole linked list
        """
        
        #set the current node starting with the head
        current = self.head
        #create a previous node to hold the one before
        #the node we want to remove
        previous = None
        
        #while current is note None then we can search for it
        while current is not None:
            #if current equals to item then we can break
            if current.data == item:
                break
            #otherwise we set previous to current and 
            #current to the next item in list
            previous = current
            current = current.get_next()
            
        #if the current is None then item, not in the list
        if current is None:
            raise ValueError(f"{item} is not in the list")
        #if previous None then the item is at the head
        if previous is None:
            self.head = current.next
            self.count -= 1
        #otherwise then we remove that node from the list
        else:
             previous.set_next(current.get_next())
             self.count -= 1
              
    def get_count(self):
        """
        Return the length of the Linked List
        Time complexity O(1) as only returning a single value
        """
        return self.count
      
    def is_empty(self):
        """
        Returns whether the Linked List is empty or not
        Time complexity O(1) as only returns True or False
        """
        #we only have to check the head if is None or not
        return self.head == None

You can then add other functionality separately such as:

  • deleteAt(index): Delete an item at a given index
  • findAt(index): Find the item at the given index
  • insertAt(index): Insert an item at a given index

This could also be extended into a doubly-linked list, whereby each node has a link to the next and also to the previous node in the linked list. You can now create a linked list that will make it easier for you to insert and remove items. the. Of course, you have to be aware of the drawbacks of non-random access and the difficulty of looking up items, but this will depend on your application of the linked list.

Hiring Now
Integral Ad Science
AdTech • Big Data • Digital Media • Marketing Tech
SHARE