Apply Insertion Sort for Singly Linked List in Python

In this tutorial, we shall apply Insertion Sort on a singly linked list in Python. For starters, a Singly Linked List is a data structure in which the elements are “linked” via pointers.

In a singly linked list, every node consists of two parts:
1. Data
2. A pointer to the next node

A class Node is created with the attributes ‘data’ and ‘next’. The push function inserts the entered elements and updates the linked list in backward order.
1. Create an empty list (sorted_list) which will finally contain our result.
2. Traverse along the cur_list and for every node, we insert it in the correct position in sorted_list.
3. Return the sorted_list.

Insertion Sort for Singly Linked List

Below is our given Python program for applying insertion sort for the singly linked list:

class Node: 
  def __init__(self, data): = data = None

def insert_sort(href): 
  sorted_list = None
  cur_list = href 
  while (cur_list != None):  
    next =
    sorted_list = sort(sorted_list, cur_list) 
    cur_list = next
  href = sorted_list
  return href 

def sort(href, node): 
  current = None
  if (href == None or >= = href 
    href = node 
    current = href 
    while ( != None and < 
      current = = = node 
  return href 

def printlist(head): 
  temp = head 
  while(temp != None): 
    temp =

def push(href, data): 
  node = Node(0) = data = href
  href = node 
  return href

# Driver program to test above functions 
a = None
a = push(a, 15) 
a = push(a, 42) 
a = push(a, 31) 
a = push(a, 12) 
a = push(a, 100) 

a = insert_sort(a) 
print("\nLinked List after sorting ") 



Linked List after sorting 

Thank You for Reading and Keep Learning 🙂

Leave a Reply