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.
- Takes the data and initializes a new node containing the passed in data
- Traverses the list and determines where to insert
- Inserts into the list
- 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.
- Locate the head of the Linked List
- Set the head to the current element we are searching
- If the head is not
None
then we compare the data - If the current node’s data matches the data we are looking for we return the current node
- 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
- 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.
- We start at the linked list’s head
- We set the current node to the head
- We set the last known node to None
- We set a flag indicating that we have found the node we want to delete
- If the current node is not None and we haven’t triggered our flag we can continue
- If the current node’s data equals the data we are looking to delete then we set our flag to true
- 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.
- We then repeat the process starting at 5 until we have no current node or the flag has been triggered
- If the current node is None then we raise an exception because our linked list does not have the data we wish to delete
- 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
- 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.
- Set the current node to the head
- Initialize the counter variable
- while the current node is not None we continue
- If the current node’s data equals the data we are looking for then increment the counter by one
- Set the current node to the current node’s next node and repeat from step 3
- 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.
- Set the current node to the head
- Initialize the counter variable
- while the current node is not None we continue
- We increment the counter by one
- Set the current node to the current node’s next node and repeat from step 3
- 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.
- Set the current node to the head of the linked list
- If the current node is not None then we print the data and a separator
- 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!