Linked list in Python

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.

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.

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.

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.

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.

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.

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 :

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.

 llist = LinkedList() 

This code line initializes an empty node in the list object.

Appending nodes

Let’s add some data to this node.

llist.head = Node(2)

Create a few other nodes for the linked list.

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 :

llist.head.next_node = s
s.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.

llist.Display();

Output the size of the list

To output the list size, call the above size function.

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.

llist.insert_at_head(6)

We can print the list to verify.

llist.Display()

Get next node from List

To get the next node:

print(llist.get_next_node(s))

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 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.data
if __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()