Data Structures

What is a linked list in python?

A linked list is a collection of elements in a sequence. This collection is connected via a one-way link. We will cover a singly linked list in python structure and implementation in this tutorial. Each element or node within the singly linked list holds a connection to another node.

As it currently exists there is no linked list in the standard python library. A singly linked list creates a single and one-directional link from one node to another node.

Traversal of a linked list means you begin at a start node and continue until no more nodes are left. Insertion, deletion, and maintaining must take into account the different nodes and the general properties surrounding a linked list.

We will cover the insertion, deletion, and some utilities of a linked list in python.

Linked List: Pro Vs Con

At the most fundamental level, a linked list is a string of nodes that can be manipulated, increased, and decreased.

Pro

The biggest pro to a linked list data structure is that it is dynamically allocated. If you compare this to a static array that is generally statically allocated then you can see how a growable collection could come in handy.

The dynamic nature of a linked list means we are able to maintain a collection of data without having to worry about determining the number of elements beforehand.

Con

The linked list data structure’s dynamic ability comes at a cost. Dynamic memory allocation increases the amount of space needed so the list can grow and adjust for overhead such as metadata and lookup times are slower than the previously mentioned static array.

The dynamic nature of a linked list means much more expensive lookups and more space is needed for the list to grow and to make room for the overhead of metadata.

Creation of a node in python

Before we can begin building out the logic for a linked list in python, we must go over a node and it’s general properties.

The node is where the main data is stored and a pointer, a reference, to the next node in the list.

The following is a simplified node class for our linked list in python.

class LinkedListNode(object):

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def get_data(self):
        return self.data

    def get_next_node(self):
        return self.next_node

    def set_next_node(self, new_next_node):
        self.next_node = new_next_node

Lets break down the above code as follows.

def __init__(self, data=None, next_node=None):
    self.data = data
    self.next_node = next_node

Initializes the node with the data and next_node with None as a default value. If another value is passed in then the None is ignored.

def get_data(self):
    return self.data

def get_next_node(self):
    return self.next_node

The LinkedListNode class also has getters for both the data and the next_node. This allows us to obtain the data and next node for any node we can access as we traverse the linked list.

def set_next_node(self, new_next_node):

Lastly, this allows us to set the next_node property of a node to the next node in our list.

Now that we have a basic node we can begin implementing our singly linked list in python.

 The Linked List in Python Implementation

Our simple linked list will be able to Insert, Search, Delete, and determine the size of the collection of the linked list.

Linked List Head/Start

We must first create a ‘head node’ or ‘starting node’ where we can begin traversing the linked list. The list is created and contains no nodes so our head node is created without having to set the next_node property because there is no next node yet.

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

This creates the linked list and sets the head of the list to the node passed in or asNone by default.

Linked List Insertion

The insert method we will be creating and in general works similarly to the following steps.

1. Takes the data and initializes a new node containing the passed in data
2. Traverses the list and determines where to insert
3. Inserts into the list
4. Updates next_node as need be

A linked list has no technical limitation as to where the node should be inserted but to keep the list in logical order the node is placed at the head of the list and the next_node property is then set to the next node in the sequence.

def insert_node(self,data):
    new_node = LinkedListNode(data)
    new_node.set_next_node(self.head)
    self.head = new_node

So now to break down the function.

When the function insert_node(self,data): is called we are passing in ourselves and the data that will make up the new node. Then we create a new LinkedListNode with the data that was passed into the function. Once we have a new node we set theset_next property to the current head. Setting the new node’s next property means we have attached the new node to the list of nodes. Lastly, we then set the head of our linked list to our new node, thus finishing the insertion process.

Time Complexity of a linked list insertion

We have not covered time complexity in depth in this article but we will cover this essential computer science concept in a later article.

A simplified idea of Time Complexity is how can you justify and measure, using math, the cost and performance of running this portion of the program if the input was an infinite amount of elements.

The implementation of insertion above is a constant of O(1). This complexity means that if we get a million elements it will still only take 1 step to complete the expected operation for each insertion.

Linked List Search

A linked list is still a collection of elements. We must be able to locate nodes so that we can update or delete them. The search function we will be creating has logic similar to the following.

1. Locate the head of the Linked List
2. Set the head to the current element we are searching
3. If the head is not None then we compare the data
4. If the current node’s data matches the data we are looking for we return the current node
5. If it does not match go to the next node and repeat the process by setting the current node to our current node’s next node
6. If we finish checking every node in the linked list and no match was found notify that the element does not exist in the list

A linked list’s search function is very important to maintaining and update the collection. Below is the actual code following logic similar to the above pseudo code.

def search_for_node(self, data):
    current_node = self.head
    while current_node is not None:
        if current_node.get_data() == data:
            return current_node
        else:
            current_node = current_node.get_next_node()
    raise ValueError("Data not found")

So now to break down the function.

First, we set the head of our linked list to the current node we are searching. If the current_node is an object and not None then we can continue to go through the list. If the current node contains the data we want we return the node and that finishes the execution of the function. If the current node does not have the data we want then we make our current node the next node in the list and repeat the cycle. If we have finished going through the whole linked list and we did not find the data we are looking for then we throw an exception noting that the data does not exist in the element.

Time Complexity of a linked list search

The implementation of the search above is a linear O(n). This complexity means that if we get a million elements it will still only take, in a worse scenario, a million steps to complete the expected operation for each search.

The reason we determine that it will be a worse case O(n) is that we have to go through each element in the list to see if it contains the data and if nothing contained only then can we say the list doesn’t contain the element. Consequentially, if there are a million items we must search a million items. The cost of the search is directly related to the size of the list.

Linked List Delete

Our Linked List Delete functionality follows a very similar logic to the search described above. The most notable difference is that we must remove the element from the list if it is found!

The deletion does require that we know the last known node so that when we delete the node we want we can reorder the next_node property to reflect the deletion.

The deletion functionality has logic similar to the following.

1. We start at the linked list’s head
2. We set the current node to the head
3. We set the last known node to None
4. We set a flag indicating that we have found the node we want to delete
5. If the current node is not None and we haven’t triggered our flag we can continue
6. If the current node’s data equals the data we are looking to delete then we set our flag to true
7. If the current node’s data does not equal the data in question we set the last known node to our current node and set our current node to the current node’s next node in the linked list.
8. We then repeat the process starting at 5 until we have no current node or the flag has been triggered
9. If the current node is None then we raise an exception because our linked list does not have the data we wish to delete
10. If the current node exists but the previous does is None then we found the data at the head and will simply point the head to the next element in the linked list
11. If the current node exists and the previous node is not None then we set the last known node’s next node property to the next node in the list. We essentially want to jump over the node we wish to delete

A linked list’s delete function vital to removing unnecessary data in our linked list. Below is the actual code following logic similar to the above pseudo code.

def delete_node(self,data):
    current_node = self.head
    last_known_node = None
    deletion_flag = False
    while current_node is not None and deletion_flag is False:
        if current_node.get_data() == data:
            deletion_flag = True
        else:
            last_known_node = current_node
            current_node = current_node.get_next_node()
    if current_node is None:
        raise ValueError("Data not found in linked list")
    if last_known_node is None:
        self.head = current_node.get_next_node()
    else:
        last_known_node.set_next_node(current_node.get_next_node())
    return current_node

Although it is not necessary to return the deleted node, we are returning it as a courtesy to whoever calls the function.

So now to break down the function.

First, we set the current node to our head, the last known node to None and the deletion flag False. A false deletion flag will indicate we have not found the node to delete. Then we go through the elements in the linked list. If the data matches we trigger the flag and begin the logic to delete. If the data does not match we then set our last known node to the current node and set the current node to the node next to be searched. Lastly, we begin the deletion logic which follows one of three cases.

• Case 1:
  • there is nothing to be deleted so throw an exception
• Case 2:
  • the element to be deleted is the head so we just increment the head
• Case 3:
  • we find the element somewhere in the list so we update the last known node to skip over the node and thus deleting it from the collection’s sequence.

Time Complexity of a linked list delete

The implementation of the delete above is a linear O(n) like the search complexity. This complexity is similar to search because we follow the same search logic to find the node we wish to delete. If there are a million items to look through to find the one we wish to delete then worse case is a million items to search.

Linked List Count

Our Linked List’s count function goes through the linked list and tells us how many elements contain the data we are looking for.

The count functionality is similar to the following.

1. Set the current node to the head
2. Initialize the counter variable
3. while the current node is not None we continue
4. If the current node’s data equals the data we are looking for then increment the counter by one
5. Set the current node to the current node’s next node and repeat from step 3
6. Return the counter variable

A linked list’s count functionality can be useful when getting ready to delete or to insert if you wish to make sure you delete all entries or to prevent from entering duplicate entries. Below is the code following the logic noted above.

def count_nodes(self,data):
    current_node = self.head
    counter = 0
    while current_node is not None:
        if current_node.get_data() == data:
            counter += 1
        current_node = current_node.get_next_node()
    return counter

So now to break down the function.

First, we set the current node to the head and initialize a counter. Next, we go through the linked list and increment a counter based on the matching data we find. Lastly, we return the counter back the whoever called the function.

Time Complexity of a linked list count

The implementation of the count above is a linear O(n) like the search complexity. This complexity is similar to search because we follow the same search logic to find all nodes that contain the data we wish to match. If there are a million items to look through to find the ones we wish to count then worse case is a million items to compare data for.

Linked List Length

Our Linked List’s length function goes through the linked list and tells us how many total elements are in the linked list.

The length functionality is similar to the following.

1. Set the current node to the head
2. Initialize the counter variable
3. while the current node is not None we continue
4. We increment the counter by one
5. Set the current node to the current node’s next node and repeat from step 3
6. Return the counter variable

A linked list’s length functionality can be useful when maintaining the list as it gives nice metadata about the list. Below is the code that follows the functionality noted above.

def linked_list_length(self):
    current_node = self.head
    counter = 0
    while current_node is not None:
        counter += 1
        current_node = current_node.get_next_node()
    return counter

So now to break down the function.

This function is very similar to the count function except we care about all nodes not just matching. First We set the current node to the head and initialize the counter. We will go through the list until we run out of nodes and increment our counter by 1. Lastly, we return the total count to the calling function.

Time Complexity of a linked list length

The implementation of the length above is a linear O(n) like the search and count complexity. This complexity is similar to search and count because we follow the same logic to find all nodes. If there are a million items to look through to get the length of the entire linked list then by definition we must go through every node to find the length of the linked list.

Linked List Print

Our Linked List’s print function is meant more as a utility function to print out the link list for the user to see it. This does become impractical if we are using a massive list.

The print functionality is similar to the following.

1. Set the current node to the head of the linked list
2. If the current node is not None then we print the data and a separator
3. Set the current node to the current node’s next node  and repeat from step 2 until we are out of nodes

A linked list’s print functionality is handy for inspecting a list, showing the user the current state of the list, and various utility purposes. Below is the code for the logic noted above.

def linked_list_print(self):
    current_node = self.head
    while current_node is not None:
        print(current_node.get_data())
        current_node = current_node.get_next_node()

so now to break down the function.

As other functions before this one, we initialize the current node to the head and the counter to zero. Then as long as the current node is not None we print the node’s data and make our current node the current node’s next node in the list. Lastly, once we are out of nodes to count we return the counter.

Time Complexity of a linked list print

The implementation of the print above is a linear O(n) like the search, count, and length complexity. This complexity is similar because we follow the same logic to go through each node but instead of searching, we are simply printing the data. If there are a million items to look through then we go through a million items and print each one.

Linked List Conclusion

We have now created a linked list in python with the ability to insert, delete, count nodes containing the specified data, determine the length of the entire linked list, and print out the linked list for inspection.

A linked list has the benefit of dynamically growing and shrinking but requires more space to grow and has the extra overhead associated with keeping the structure. The cons and benefits are generally compared to something like a statically allocated array that does not grow dynamically.

Our linked list is one of many data structures that are available to software developers. Although this specified data structure is not found in standard libraries you now have your simple version of this data structure.

NOTE: If you want to be able to save your data to a text file please feel free to check out our recommended article to learn how to Write and Read to and from a text file in Python.

The final code with example commands and output

Final Code:

class LinkedListNode(object):

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def get_data(self):
        return self.data

    def get_next_node(self):
        return self.next_node

    def set_next_node(self, new_next_node):
        self.next_node = new_next_node


class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def insert_node(self,data):
        new_node = LinkedListNode(data)
        new_node.set_next_node(self.head)
        self.head = new_node

    def search_for_node(self, data):
        current_node = self.head
        while current_node is not None:
            if current_node.get_data() == data:
                return current_node
            else:
                current_node = current_node.get_next_node()
        raise ValueError("Data not found")

    def delete_node(self,data):
        current_node = self.head
        last_known_node = None
        deletion_flag = False
        while current_node is not None and deletion_flag is False:
            if current_node.get_data() == data:
                deletion_flag = True
            else:
                last_known_node = current_node
                current_node = current_node.get_next_node()
        if current_node is None:
            raise ValueError("Data not found in linked list")
        if last_known_node is None:
            self.head = current_node.get_next_node()
        else:
            last_known_node.set_next_node(current_node.get_next_node())
        return current_node

    def count_nodes(self,data):
        current_node = self.head
        counter = 0
        while current_node is not None:
            if current_node.get_data() == data:
                counter += 1
            current_node = current_node.get_next_node()
        return counter

    def linked_list_length(self):
        current_node = self.head
        counter = 0
        while current_node is not None:
            counter += 1
            current_node = current_node.get_next_node()
        return counter

    def linked_list_print(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.get_data())
            current_node = current_node.get_next_node()

currentLinkedList = LinkedList()
currentLinkedList.insert_node(4)
currentLinkedList.insert_node(3)
currentLinkedList.insert_node(2)
currentLinkedList.insert_node(1)
currentLinkedList.linked_list_print()
print('There are ',currentLinkedList.linked_list_length())
currentLinkedList.delete_node(3)
currentLinkedList.linked_list_print()
print('Now there are ',currentLinkedList.linked_list_length())
currentLinkedList.insert_node(4)
currentLinkedList.insert_node(4)
print('There are ',currentLinkedList.count_nodes(4),' many nodes with the number 4 as data')

Output

1
2
3
4
There are  4
1
2
4
Now there are  3
There are  3  many nodes with the number 4 as data

Happy Coding!