Linked lists in Python are one of the most interesting abstract data types that have continued to stay in popularity since the C/C++ days. In this article, we’ll learn how to implement a Linked list in Python from scratch.
What is a Linked List?
A linked list is a linear data structure where each element is a separate object. The elements of a linked list, unlike an array, are not stored together in the memory.
Each element of the linked list points to the element after it. Here points mean that each element stores the address of the next element.
While traversing a linked list we use these pointers to jump from one node to the next.
For each linked list, there are a two elements that need to be considered:
- The nodes – We handle them by creating a node class
- The connection between nodes – We will handle this with the variables and lists in Python.
How to Create a Linked List in Python?
Let’s go over the steps to create a linked list in Python.
Create the Node Class
To create our own linked list we need to define a node class. Before we define a node class, we need to think about what fields should the class have.
A linked list node is supposed to store two things. These are :
- Data
- Address of the next node
Let’s define a node class with these two fields.
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
Create the Linked-List class
Let’s make another class that will initialize an empty node for creating a linked list.
class LinkedList(object):
def __init__(self, head=None):
self.head = head
There are a few important functions that will be held within this class. Let’s go over the purpose and the definition for each of these classes.
1. Function to print the list
Let’s write a function to print our linked list. To print the linked list we need to traverse through the entire list and keep printing the data from each node.
def printList(self):
temp = self.head
while (temp):
print (temp.data, " -> ", end = '')
temp = temp.next_node
print("")
2. Get size of the list
Let’s write a function that returns the size of the linked list. To calculate the size, we need to traverse through the entire list and keep a counter while doing so.
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.next_node
return count
This function will return the size of the linked list.
3. Insert a new node at the head
Let’s write a function to insert a new node at the head.
def insert_at_head(self, data):
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
This will create a new node with the data and add it before the head. It then points the head of the linked list to this new node.
4. Get Next node
The function to get next node is given below :
def get_next_node (self,node):
return node.next_node.data
Create a New Linked List
Let’s write the main function and create a linked list using the class we created above.
llist = LinkedList()
This line of code initializes the llist object with an empty node.
1. Adding nodes
Let’s add some data to this node.
llist.head = Node(1)
Create a few other nodes for the linked list.
s = Node(2)
t = Node(3)
2. Create links between the nodes
Creating links between the individual nodes is the most important part of creating a linked list.
You can create the links using :
llist.head.next_node = s
s.next_node = t
3. Print the nodes of the list
To verify whether the list was created successfully or not we can use the print function.
llist.printList()
Output:
1 -> 2 -> 3
4. Output the size of the list
To output the size of the list, call the size function we wrote above.
print(llist.size())
Output :
3
5. Insert a new node
Let’s try inserting some data at the head of the linked list using the function above.
llist.insert_at_head(5)
We can print the list to verify.
llist.printList()
Output :
5 -> 1 -> 2 -> 3
6. Get next node
To get the next node:
print(llist.get_next_node(s))
Output:
3
Complete Implementation of Linked Lists in Python
The complete implementation is given below :
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.next_node
return count
def printList(self):
temp = self.head
while (temp):
print (temp.data, " -> ", end = '')
temp = temp.next_node
print("")
def insert_at_head(self, data):
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
def get_next_node (self,node):
return node.next_node.data
if __name__=='__main__':
llist = LinkedList()
llist.head = Node(1)
s = Node(2)
t = Node(3)
llist.head.next_node = s;
s.next_node = t
llist.printList()
print(s.data)
print(llist.size())
print(llist.get_next_node(s))
llist.insert_at_head(5)
llist.printList()
Conclusion
This tutorial covered the implementation of linked lists in Python. We created our own linked list from scratch and wrote some additional functions to print the list, get the size of the list and make insertions at the head.