There are numerous data structures within programming, which as a developer are useful to know about. One of these data structures are linked lists. These are a linear data structure, where nodes are stored in different locations within memory (i.e. not next to each other). In order to interact with other nodes of a linked list, there is a pointer, which as the name suggests, “points” to the next node in the list. The last node of the list will have an empty pointer, until another node is added into the linked list.
What this looks like in practice is a series of nodes, which have a data element, for the value stored within them and a next node element that is the pointer to the next node of the list. The diagram below shows a schematic of how this works in a short list.
One term to introduce as well, that is in the diagram above, is the “head node”, this is the first node in the linked list.
So where are linked lists used?? Well linked lists can be used for implementing stacks and queues, as well as more complicated data structures, such as graphs. Linked lists allow for the traversal of the list in a set order and the controlled insertion or deletion of nodes from the start or end of the list.
Implementing linked lists in Python
Python does have a module called “collections” that does have an implementation of linked lists already. However, for this article I’ll go through creating a custom linked list class and working with that.
The first stage of setting up the linked list is to create the node class, this will be an object with a data element and a pointer to the next node. There will also be a representation (__repr__) function to display the details of the node.
class Node:
def __init__(self, data):
self.data = data
self.next_node = Null def __repr__(self):
return f"Node contains: {self.data}"
This allows for the node object to be created and allows for the manual linking of the next node, by altering the next_node attribute once created.
first_node = Node(1)
second_node = Node(2)
third_node = Node(3)first_node.next_node = second_node
second_node.next_node = third_node
Lets see what this looks like at the moment…
Now we could leave this here and this is a linked list. However, there is no way to know here where the first node is and iterating through it is a bit clunky. Also there is the issue that the list doesn’t have a variable name, there are only identifiers for the nodes themselves.
So to get around these issues and enable we can create a new class to handle our list, with functions in it to handle adding nodes to the list and displaying the list. When adding nodes to the list, there are a number of checks that need to be performed before the node can be added. Firstly, is the list empty, if it is then the head of the list can be updated with the new node. If it isn’t, then then we need to iterate over the list until we get to a node that has a next_node value of None. This will be the last node of the list as it stands. When this node has been found, the next_node can be updated to contain a new node with the data specified.
The logic of looping through all nodes in the list to find the end can be applied when representing the list as well.
class LinkedList:
def __init__(self):
self.head = None
def add_node(self, data):
if not self.head:
self.head = Node(data)
else:
current_node = self.head
while current_node.next_node:
current_node = current_node.next_node
current_node.next_node = Node(data)
def __repr__(self):
current_node = self.head if not current_node:
return "Empty list" output = ""
count = 0
while current_node.next_node:
output += f"Position {count}: {current_node} \n"
count += 1
current_node = current_node.next_node
output += f"Position {count}: {current_node}"
return output
In the LinkedList class there are some checks in there to valid handle if the list is empty (self.head is None). This would be the case if looking at the list immediately after creating the list. Otherwise, providing there is a starting node, then the while loop will move along the nodes of the list until it reaches one with nothing in the next_node attribute. Each step through the linked list will add a string to the output that will capture the current position and the current node. The current position is a count that is updated each time through the while loop. When the final node is reached the while loop is broken and the details of that node added to the output.
So lets see this in action…
Conclusion
Great, that’s worked as expected. Now that the linked list is in this format, there are a number of additional functions that could be added to this class (and will be in future articles). These include reversing the whole list or part of the linked list and removing nodes from the list, as well as others.
I hope that following along with this tutorial has given you a demonstration of how to create a linked list, add nodes to it and how to represent it.
