Insertion Sort for Singly Linked List | Pyhton implementation of above algorithm ; A utility function to insert a node at the beginning of linked list ; allocate node ; link the old list off the new node ; move the head to point to the new node ; function to sort a singly linked list using insertion sort ; Initialize sorted linked list ; Traverse the given linked list and insert every node to sorted ; Store next for next iteration ; insert current in sorted linked list ; Update current ; Update head_ref to point to sorted linked list ; function to insert a new_node in a list . Note that this function expects a pointer to head_ref as this can modify the head of the input linked list ( similar to push ( ) ) ; Special case for the head end ; Locate the node before the point of insertion ; BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert Function to print linked list ; Driver program to test above functions
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def push ( head_ref , new_data ) : NEW_LINE INDENT new_node = Node ( 0 ) NEW_LINE new_node . data = new_data NEW_LINE new_node . next = ( head_ref ) NEW_LINE ( head_ref ) = new_node NEW_LINE return head_ref NEW_LINE DEDENT def insertionSort ( head_ref ) : NEW_LINE INDENT sorted = None NEW_LINE current = head_ref NEW_LINE while ( current != None ) : NEW_LINE INDENT next = current . next NEW_LINE sorted = sortedInsert ( sorted , current ) NEW_LINE current = next NEW_LINE DEDENT head_ref = sorted NEW_LINE return head_ref NEW_LINE DEDENT def sortedInsert ( head_ref , new_node ) : NEW_LINE INDENT current = None NEW_LINE if ( head_ref == None or ( head_ref ) . data >= new_node . data ) : NEW_LINE INDENT new_node . next = head_ref NEW_LINE head_ref = new_node NEW_LINE DEDENT else : NEW_LINE INDENT current = head_ref NEW_LINE while ( current . next != None and current . next . data < new_node . data ) : NEW_LINE INDENT current = current . next NEW_LINE DEDENT new_node . next = current . next NEW_LINE current . next = new_node NEW_LINE DEDENT return head_ref NEW_LINE DEDENT def printList ( head ) : NEW_LINE INDENT temp = head NEW_LINE while ( temp != None ) : NEW_LINE INDENT print ( temp . data , end = " ▁ " ) NEW_LINE temp = temp . next NEW_LINE DEDENT DEDENT a = None NEW_LINE a = push ( a , 5 ) NEW_LINE a = push ( a , 20 ) NEW_LINE a = push ( a , 4 ) NEW_LINE a = push ( a , 3 ) NEW_LINE a = push ( a , 30 ) NEW_LINE print ( " Linked ▁ List ▁ before ▁ sorting ▁ " ) NEW_LINE printList ( a ) NEW_LINE a = insertionSort ( a ) NEW_LINE print ( " Linked List after sorting   " ) NEW_LINE printList ( a ) NEW_LINE