Python - Linked List

A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the link to the next node as shown in the below image:

The first node also known as HEAD is always used as a reference to traverse the list. The last node points to NULL. Linked list can be visualized as a chain of nodes, where every node points to the next node.

Types of Linked List

The types of linked list are mentioned below:

Singly Linked List: can be traversed only in forward direction.
Doubly Linked List: can be traversed in forward and backward directions.
Circular Singly Linked List: Last element contains link to the first element as next.
Circular Doubly Linked List: Last element contains link to the first element as next and the first element contains link of the last element as previous.

Implementation of Singly Linked List

Representation:

In Python, singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

Create a Singly Linked List

Let us create a simple singly linked list which contains three data nodes.

# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None
 
# test the code   
# create an empty LinkedList                 
MyList = LinkedList()

#Add first node.
first = Node(10)
#linking with head node
MyList.head = first

#Add second node.
second = Node(20)
#linking with first node
first.next = second

#Add third node.
third = Node(30)
#linking with second node
second.next = third

Traverse a Singly Linked List

A singly linked list can be traversed using a temp node. Keep on moving the temp node to the next one and displaying its content. At the end of the list, the temp node will become NULL.

# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      print()
    else:
      print("The list is empty.")

# test the code    
# create an empty LinkedList                 
MyList = LinkedList()

#Add first node.
first = Node(10)
#linking with head node
MyList.head = first

#Add second node.
second = Node(20)
#linking with first node
first.next = second

#Add third node.
third = Node(30)
#linking with second node
second.next = third

#print the content of list 
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30