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): 
    self.data = data 
    self.next = None

def insert_sort(href): 
  sorted_list = None
  cur_list = href 
  while (cur_list != None):  
    next = cur_list.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.data >= node.data): 
    node.next = href 
    href = node 
  else: 
    current = href 
    while (current.next != None and current.next.data < node.data): 
      current = current.next
    node.next = current.next
    current.next = node 
  return href 

def printlist(head): 
  temp = head 
  while(temp != None): 
    print(temp.data) 
    temp = temp.next

def push(href, data): 
  node = Node(0)  
  node.data = data 
  node.next = 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 ") 
printlist(a) 

Output

Linked List after sorting 
12
15
31
42
100

Thank You for Reading and Keep Learning 🙂

• Also Read: Bogo Sort in Python