Python is an open-source language and does not have a built-in linked list in its standard library, and it is possible to get a linked list in python using a particular implementation. In this article, we’ll learn how to build a linked list in Python.
We’ll be covering the following topics in this tutorial:
What is Linked List in Python?
The Linked List is a linear data structure made of multiple objects called nodes with a common data type. Each node includes both data and a reference to the next node in the list. The head point means the first node, and the last element in the list points to null. When the list is empty, the head pointer points to null.
Why use linked lists?
The linked list is often compared to arrays. Whereas an array is a fixed size, a linked list will dynamically allocate to its elements. What are the benefits and drawbacks of these features? Here are some of the most important:
Advantages
• A linked list saves memory. It just assigns the memory used to store values. You would need to set the array size in arrays before you fill it with values, potentially wasting memory.
• Linked list nodes will exist in the memory. Whereas an array requires a sequenced memory to initialize, as long as the references are modified, each linked list node can be flexibly moved to a different address.
• In several cases, linked list implements due to their dynamic size and simplicity of addition and deletion.
• It is used to implement several complicated data structures, such as the graph adjacency list.
• They are used for the management of lifecycles in operating systems.
• A playlist is implemented in a music application utilizing a double-linked list.
• Blockchain, a complex data structure used for cryptocurrencies and ledgers, uses a linked list at its core.
Disadvantages
When searching for a value in a linked list, begin from the beginning of the list and look for a value, you want one element at a time. If there are n elements in the linked list, this can take up to n time. On the opposite, certain languages enable continuous array queries.
linked list implementation
Let’s go over the steps to create a linked list in Python.
Create the Node Class
To build the linked list, a node class must specify. Until defining a node class, we must think about the fields the class could provide.
Two items can be placed in a linked list node. The following are:
• Data
• Reference of the next node
Let’s define a node class with these two fields.
1 2 3 4 | class Node: def __init__(self,data): self.data = data self.next = None # the pointer initially points to null |
Create the Linked-List class
Let’s construct another class that initializes an empty node to create a linked list.
1 2 3 | class LinkedList(object): def __init__(self, head = None): self.head = head |
There are a variety of essential functions in this class. Let’s go over the intent for each of these classes and the definition.
Function to print the linked list
Let’s compose a printing functionality for our linked list. To print the linked list, we must go through the whole list and begin to print data from every node.
1 2 3 4 5 6 | def Display(self): temp = self.head while (temp): print (temp.data, " -> ", end = '') temp = temp.next_node print("") |
Get size of the Linked list
Let’s write functionality that returns the linked list size. To determine the size, we must traverse through the whole list and hold a counter for it.
1 2 3 4 5 6 7 | def size(self): current = self.head count = 0 while current: count += 1 current = current.next_node return count |
Insert a new node at the head of a linked list
Let’s write a functionality to insert a new head node.
1 2 3 4 | def insert_at_head(self, data): new_node = Node(data) new_node.next_node = self.head self.head = new_node |
It introduces a new data node and connects it to the head. The linked list header is then directed to this new node.
Get Next node
The function to get next node is given below :
1 2 | def get_next_node (self,node): return node.next_node.data |
Create a New Linked List
Write the primary function and render a linked list using the above class.
1 | llist = LinkedList() |
This code line initializes an empty node in the list object.
Appending nodes
Let’s add some data to this node.
1 | llist.head = Node(2) |
Create a few other nodes for the linked list.
1 2 | s = Node(3)t = Node(4) |
Create links between the nodes of List
The most critical aspect of building a linked list is creating connections between the specific nodes.
You can create the links using :
1 2 | llist.head.next_node = ss.next_node = t |
Print the nodes of the Linked list
We may use the print function to confirm whether or not the list was generated successfully.
1 | llist.Display(); |
Output the size of the list
To output the list size, call the above size function.
1 | print(llist.size()) |
Insert a new node in the Linked List
Try to insert any data at the top of the linked list using the above function.
1 | llist.insert_at_head(6) |
We can print the list to verify.
1 | llist.Display() |
Get next node from List
To get the next node:
1 | print(llist.get_next_node(s)) |
Implementation of Linked Lists in Python
The complete implementation is given below :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Node(object): def __init__(self, data=None, next_node=None): self.data = data self.next_node = next_nodeclass 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 Display(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.dataif __name__=='__main__': llist = LinkedList() llist.head = Node(2) s = Node(3) t = Node(4) llist.head.next_node = s; s.next_node = t llist.Display() print(s.data) print(llist.size()) print(llist.get_next_node(s)) llist.insert_at_head(10) llist.Display() |
Dinesh Thakur holds an B.C.A, MCDBA, MCSD certifications. Dinesh authors the hugely popular