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?
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.
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.
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.
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
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 == NoneYou can then add other functionality separately such as:
deleteAt(index): Delete an item at a given indexfindAt(index): Find the item at the given indexinsertAt(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.
