Python programming language is an open-source language with various out-of-the-box implementations that makes it unique and easier to learn. Although Python does not support the concept of a linked list, there is a way around it through a different implementation to get a linked list. In this article, we will learn how we can make a linked list in Python. Following are the topics covered in this blog:
What is Linked List?
The link list is a sequence of nodes having a similar data type, each node contains one data object and pointer to the next node.
A linked list is a linear data structure with the collection of multiple nodes. Where each element stores its own data and a pointer to the location of the next element. The last link in a linked list points to null, indicating the end of the chain. An element in a linked list is called a node. The first node is called the head. The last node is called the tail.
Now that we learned about what is Linked. So let’s move on to implementing a Linked list.
Implementing a Linked List
For creating a Linked List, we create a node object and create another class to use this node object.
Code for creating Node class.
The above program creates a linked list with three data elements.
class Node(object): # Constructor to initilize class variables def __init__(self, data=None, next_node=None): self.data = data self.next_node = next_node #get data def get_data(self): return self.data # get next value def get_next(self): return self.next_node # set next data def set_next(self, new_next): self.next_node = new_next
Implementation of link list consists of the following functionality in a linked list
1. Insert: This method will insert a new node in a linked list.
2. Size: This method will return the size of the linked list.
3. Search: This method will return a node containing the data, else will raise an error
4. Delete: This method will delete a node containing the data, else will raise an error
Lets see the Methods of Linked list
Init method in a linked list
class LinkedList(object): def __init__(self, head=None): self.head = head
Init method is used for the initialization of a class variable if the list has no nodes it is set to none.
Insert:
def insert(self, data): new_node = Node(data) new_node.set_next(self.head) self.head = new_node
This insert method takes data, initializes a new node with the given data, and adds it to the list. Technically you can insert a node anywhere in the list, but the simplest way to do it is to place it at the head of the list and point the new node at the old head (sort of pushing the other nodes down the line).
Size
# Returns total numbers of node in list def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() return count
The size method is very simple, it basically counts nodes until it can’t find anymore, and returns how many nodes it found. The method starts at the head node, travels down the line of nodes until it reaches the end (the current will be None when it reaches the end) while keeping track of how many nodes it has seen.
Search
# Returns the node in list having nodeData, error occured if node not present
def search(self, nodeData):
current = self.head
isPresent = False
while current and isPresent is False:
if current.get_data() == nodeData:
isPresent = True
else:
current = current.get_next()
if current is None:
raise ValueError("Data not present in list")
return current
Search is actually very similar to size, but instead of traversing the whole list of nodes it checks at each stop to see whether the current node has the requested data. If so, returns the node holding that data. If the method goes through the entire list but still hasn’t found the data, it raises a value error and notifies the user that the data is not in the list.
Delete
# Remove the node from linked list returns error if node not present
def delete(self, nodeData):
current = self.head
previous = None
isPresent = False
while current and isPresent is False:
if current.get_data() == nodeData:
isPresent = True
else:
previous = current
current = current.get_next()
if current is None:
raise ValueError("Data not present in list")
if previous is None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())
The delete method traverses the list in the same way that search does, but in addition to keeping track of the current node, the delete method also remembers the last node is visited. When delete finally arrives at the node it wants to delete. It simply removes that node from the chain by “leapfrogging” it.
By this I mean that when the delete method reaches the node it wants to delete, it looks at the last node it visited (the ‘previous’ node) and resets that previous node’s pointer. Rather than pointing to the soon-to-be-deleted node.
It will point to the next node in line. Since no nodes are pointing to the poor node that is being deleted, it is effectively removed from the list!
Master the art of removing elements from Python lists with ease – explore our comprehensive guide now
This brings us to the end of this article where we have learned how we can make a linked list in python with a similar implementation even though python does not really support the concept of a linked list. I hope you are clear with all that has been shared with you in this tutorial.
If you found this article on “Linked List In Python” relevant, check out the Edureka Python Certification Training. A trusted online learning company with a network of more than 250,000 satisfied learners spread across the globe.
We are here to help you with every step on your journey and come up with a curriculum that is designed for students and professionals who want to be a Python developer. The course is designed to give you a head start into Python programming and train you for both core and advanced Python concepts along with various Python frameworks like Django.
If you come across any questions, feel free to ask all your questions in the comments section of “Linked List In Python” and our team will be glad to answer.