In this article we will focus on a complete walk through of a Python linked list data structure.
Table of Contents
- What is a linked list
- How to create a linked list in Python
- How to traverse a linked list in Python
- How to insert a node at the end of a linked list in Python
- How to insert a node at the beginning of a linked list in Python
- How to insert a node after a given node of a linked list in Python
- How to search a node in a linked list in Python
- How to delete a node from a linked list in Python
- Conclusion
What is a linked list
A linked list is a data structure that consists of nodes, where each node contains two fields:
- Value
- Pointer (reference link) to the next node
It is a collection of nodes which make a sequence using the pointers, where the first node of the linked list is called the head node, and the last node has a reference link to NULL.
How to create a linked list in Python
We already know that a linked list is a sequence made from nodes.
The first step to creating a linked list is to create a structure of a node (as its own class).
When initialized, a node should take some data to use as the value, as well as have a default pointer to next node set to None, which will be changed as we add more nodes together to form a sequence.
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
To test the code, let’s create a node that will have a value equal to 5, and print out the value and the pointer to next node:
first_node = Node(5)
print(first_node.data)
print(first_node.next_node)
And you should get:
5 None
As we expected, the values stored is 5 and reference link to next node is None.
Let’s go ahead and create a few more individual nodes:
second_node = Node(7)
third_node = Node(15)
At this point we have three nodes which are not connected to each other: first_node, second_node, third_node.
The next step is to create a structure for a linked list (as its own class).
When initialized, a linked list should only have the head node set to NULL, in order to start an empty linked list:
class LinkedList:
def __init__(self):
self.head = None
To start adding nodes to a linked list we want the first_node we created to be the head node of the linked list:
llist = LinkedList()
llist.head = first_node
This will create a linked list with one node (which will be the head node).
Recall that each node has a reference link set to NULL. In order to create a sequence of nodes, we will set each reference link to point to the next node:
llist.head.next_node = second_node
second_node.next_node = third_node
And now we have successfully created a linked list with three nodes which should look like this:
In this section we have been adding nodes to the linked list rather manual than programmatically. In the next sections we will explore to to insert nodes at the end, and the beginning, and at a specific position of the linked list.
How to traverse a linked list in Python
In the previous section we created the linked list llist and now we would like to traverse the linked list and print out values of each node.
Recall that the initial construction of linked list is given by:
class LinkedList:
def __init__(self):
self.head = None
A singly linked list can only be traversed in forward direction.
The logic is fairly simple: we will start at the head node, print its current value, and move to the next node (given that the reference link is not NULL).
We will continue moving to the next node as long as the node has data in it.
In this section we will implement a method print_llist() for traversing a linked list and printing values of each node for the LinkedList() class.
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
It will be added as a method of the LinkedList() class:
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedList:
def __init__(self):
self.head = None
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
Let’s test create the same list as in the previous section and print out the values of each node:
llist = LinkedList()
llist.head = first_node
llist.head.next_node = second_node
second_node.next_node = third_node
llist.print_llist()
And you should get:
5 7 15
How to insert a node at the end of a linked list in Python
In the one of the previous sections we showed an example of how to create a linked list in Python.
The approach we used was rather manual then programmatic because we had to manually link the nodes together and add reference links to the next node.
In this section we will implement a method insert_at_end() for inserting nodes at the end of a linked list (basically appending new nodes) for the LinkedList() class.
Let’s reuse the linked list we have built in the previous section:
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedList:
def __init__(self):
self.head = None
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
In order to add nodes at the end of the linked list in Python, we should follow a logic that is similar to traversing the linked list in Python.
We start at the head node:
- if the head node exists, then we move to the next node
- if the head node is NULL, then the node we want to add becomes the head node
Assuming that the head node exists, we move to the next node (given that the reference link is not NULL).
We will continue moving to the next node as long as the reference link is pointing to another node that has a value and it’s not the last node (with reference link NULL).
Once we reach the last node, we will insert the new node right after it, and have its reference link as NULL.
In this section we will implement a method insert_at_end() for inserting nodes at the end of a linked list for the LinkedList() class.
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next_node is not None:
last_node = last_node.next_node
last_node.next_node = new_node
It will be added as a method of the LinkedList() class:
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next_node is not None:
last_node = last_node.next_node
last_node.next_node = new_node
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
Now let’s try to create the same list as in the second section of this tutorial and see if we get the same results:
llist = LinkedList()
llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.print_llist()
And you should get:
5 7 15
which is exactly the same as when we created the linked list manually.
Using the insert_at_end() method we can add more nodes at the end of a linked list in Python.
How to insert a node at the beginning of a linked list in Python
In the previous section we implemented a method to insert nodes at the end of a linked list.
But what if we need to add a node in the beginning of a linked list? That’s what we are going to cover in this section!
Inserting a node in the beginning of a linked list is much simpler from the logic and code perspective.
The very first node of a linked list is a head node, and if we need to insert a node before it, we should simply have a node that has a reference link to the head node (of course, if there are no nodes in the linked list, then the new node becomes the head node).
In this section we will implement a method insert_at_beginning() for inserting nodes at the beginning of a linked list for the LinkedList() class.
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
new_node.next_node = self.head
self.head = new_node
It will be added as a method of the LinkedList() class:
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next_node is not None:
last_node = last_node.next_node
last_node.next_node = new_node
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
new_node.next_node = self.head
self.head = new_node
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
Now let’s create the same list as in the previous section of this tutorial and and add a node with value “9” at the beginning of the linked list:
llist = LinkedList()
llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.insert_at_beginning(9)
llist.print_llist()
And you should get:
9 5 7 15
Using the insert_at_beginning() method we can add more nodes at the beginning of a linked list in Python.
How to insert a node after a given node of a linked list in Python
So far in this tutorial we discussed how to add elements at the beginning and at the end of a linked list in Python.
In this section we will explore how to add elements after a given node of a linked list in Python.
When inserting a node after a given node, the first step is to find the previous node in the linked list.
In order to find the previous node, we will traverse the linked list from its head node, all the way until we find the previous node.
Once we find the previous node, we will change the reference link of a new node from NULL to the reference link of the previous node, and then we will change the reference link of the previous node to the new node.
In this section we will implement a method insert_after_node() for inserting nodes after a given node of a linked list for the LinkedList() class.
def insert_after_node(self, data, previous_node):
new_node = Node(data)
current_node = self.head
while current_node.data != previous_node:
current_node = current_node.next_node
new_node.next_node = current_node.next_node
current_node.next_node = new_node
It will be added as a method of the LinkedList() class:
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next_node is not None:
last_node = last_node.next_node
last_node.next_node = new_node
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = newnode
return
new_node.next_node = self.head
self.head = new_node
def insert_after_node(self, data, previous_node):
new_node = Node(data)
current_node = self.head
while current_node.data != previous_node:
current_node = current_node.next_node
new_node.next_node = current_node.next_node
current_node.next_node = new_node
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
Now let’s create the same list as in the previous section of this tutorial and add a node with value “10” after the node with value “7” the linked list:
llist = LinkedList()
llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.insert_at_beginning(9)
llist.insert_after_node(10,7)
llist.print_llist()
And you should get:
9 5 7 10 15
Using the insert_after_node() method we can add a node after a given node of a linked list in Python.
How to search a node in a linked list in Python
We already know how to create a linked list, and let’s say we created a linked list in Python.
Now we would like to search a node in this linked list to check whether it exists.
The logic is fairly simple: we will start at the head node and start moving to the next node (node after node and given that the reference link is not NULL).
We will compare the values of each node with the value we are searching, and print “Node found” as soon as the node is found, or print “Node not found” if we traversed the linked list and didn’t find the value we are searching.
In this section we will implement a method search_node() for searching a node in the linked list for the LinkedList() class.
def search_node(self, data):
current_node = self.head
while current_node is not None:
if current_node.data == data:
print('Node found')
return
current_node = current_node.next_node
print('Node not found')
It will be added as a method of the LinkedList() class:
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next_node is not None:
last_node = last_node.next_node
last_node.next_node = new_node
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = newnode
return
new_node.next_node = self.head
self.head = new_node
def insert_after_node(self, data, previous_node):
new_node = Node(data)
current_node = self.head
while current_node.data != previous_node:
current_node = current_node.next_node
new_node.next_node = current_node.next_node
current_node.next_node = new_node
def search_node(self, data):
current_node = self.head
while current_node is not None:
if current_node.data == data:
print('Node found')
return
current_node = current_node.next_node
print('Node not found')
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
Now let’s create the same list as in the previous section of this tutorial and search for the node with value “15”:
llist = LinkedList()
llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.insert_at_beginning(9)
llist.insert_after_node(10,7)
llist.search_node(15)
And you should get:
Node found
Using the search_node() method we can search a node in a linked list in Python.
How to delete a node from a linked list in Python
We already know how to search a node in a linked list in Python.
Now we would like to delete a node from a linked list in Python.
As you can imagine, the process will be similar to traversing a linked list and searching for a given node in a linked list.
The logic is fairly simple: we will start at the head node and check whether it’s the node we would like to remove:
- If yes, then we will repoint the head node to the next node.
- If no, then we will use it as current node, and check whether we want to remove the next node (the process continues node after node until we find the node to delete from a linked list).
In this section we will implement a method delete_node() for deleting a node from the linked list for the LinkedList() class (this method assumes you are trying to delete a node that exists in a linked list).
def delete_node(self, data):
current_node = self.head
if self.head.data == data:
self.head = current_node.next_node
return
while current_node.next_node.data != data:
current_node = current_node.next_node
current_node.next_node = current_node.next_node.next_node
It will be added as a method of the LinkedList() class:
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next_node is not None:
last_node = last_node.next_node
last_node.next_node = new_node
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = newnode
return
new_node.next_node = self.head
self.head = new_node
def insert_after_node(self, data, previous_node):
new_node = Node(data)
current_node = self.head
while current_node.data != previous_node:
current_node = current_node.next_node
new_node.next_node = current_node.next_node
current_node.next_node = new_node
def search_node(self, data):
current_node = self.head
while current_node is not None:
if current_node.data == data:
print('Node found')
return
current_node = current_node.next_node
print('Node not found')
def delete_node(self, data):
current_node = self.head
if self.head.data == data:
self.head = current_node.next_node
return
while current_node.next_node.data != data:
current_node = current_node.next_node
current_node.next_node = current_node.next_node.next_node
def print_llist(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next_node
Now let’s create the same list as in the previous section of this tutorial and delete the node with value “5”:
llist = LinkedList()
llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.insert_at_beginning(9)
llist.insert_after_node(10,7)
llist.delete_node(5)
llist.print_llist()
And you should get:
9 7 10 15
Using the delete_node() method we can delete a node from a linked list in Python.
Conclusion
This article is an introductory walkthrough for linked list data structure in Python and its functionality which is important to learn as they are used in many areas of programming and in machine learning.
Feel free to leave comments below if you have any questions or have suggestions for some edits and check out more of my Data Structures articles.
