Algorithm
The approach that we will be using for sorting the list using the insertion sort for linked lists is majorly the idea of inserting a node in a sorted linked list that too in a sorted fashion. The approach here can be iteratively used to build the solution in pieces, and this is what we will use here. At every step, i.e for each of the nodes that we will traverse in the linked list follow the following series of steps.
- The first step will be to check whether the linked list is empty and if empty then make the node as the head and return it.
- Check whether the value of the node that is required to be inserted is smaller than the value of the head node, then insert the node at the start and make it head.
- Now in a loop, we try to find the appropriate node after which each input node (let 3) is to be inserted. To find the appropriate node start from the head, and keep moving until you reach a node GN (4 in the above diagram) whose value is greater than the input node. The node just before GN is the appropriate node (2).
-
Finally, insert node (3) after the appropriate node (2) found in step 3.
Now for sorting the list using the insertion sort for linked list technique, we can use the following algorithm of which the above algorithm that we looked at would be used iteratively.
- The first step will be to create an empty sorted linked list with a head referring to a null node.
-
Now we traverse the linked list iteratively and use the same algorithm that we looked at above for sorting lists using insertion sort for linked lists.
- I.e. Inserting a node in a sorted linked list in a sorted way. (the same algorithm that was introduced above is repeated here)
- Finally, we replace the head of the linked list with the head of the new sorted linked list (resultant list) that we have obtained in the previous step.
Also read - Merge sort in linked list
Implementation
# Insertion sort for linked list in Python.
# Node class.
class Node:
# Constructor to initialize the node object.
def __init__(self, data):
self.data = data
self.next = None
# Function to sort a singly linked list using insertion sort.
def insertionSort(head_ref):
# Initialize sorted linked list.
sorted = None
# Traverse the given linked list and insert every node to sorted.
current = head_ref
while (current != None):
# Store next for next iteration.
next = current.next
# Insert current in sorted linked list.
sorted = sortedInsert(sorted, current)
# Update current.
current = next
# Update head_ref to point to sorted linked list.
head_ref = sorted
return head_ref
# 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())
def sortedInsert(head_ref, new_node):
current = None
# Special case for the head end.
if (head_ref == None or (head_ref).data >= new_node.data):
new_node.next = head_ref
head_ref = new_node
else:
# Locate the node before the point of insertion.
current = head_ref
while (current.next != None and
current.next.data < new_node.data):
current = current.next
new_node.next = current.next
current.next = new_node
return head_ref
# Function to print linked list.
def printList(head):
temp = head
while(temp != None):
print( temp.data, end = " ")
temp = temp.next
# A utility function to insert a node at the beginning of linked list.
def push( head_ref, new_data):
# Allocate node.
new_node = Node(0)
# Put in the data.
new_node.data = new_data
# Link the old list off the new node.
new_node.next = (head_ref)
# Move the head to point to the new node.
(head_ref) = new_node
return head_ref
# Main program to test all the above functions.
a = None
a = push(a, 5)
a = push(a, 2)
a = push(a, 4)
a = push(a, 6)
a = push(a, 1)
a = push(a, 3)
print("Linked List before insertion sort:")
printList(a)
a = insertionSort(a)
print("\nLinked List after insertion sort:")
printList(a)

You can also try this code with Online Python Compiler
Run Code
Output
Linked List before insertion sort:
3 1 6 4 2 5
Linked List after insertion sort:
1 2 3 4 5 6

You can also try this code with Online Python Compiler
Run Code
Complexity Analysis
-
Time Complexity: The time complexity of performing insertion sort for the linked list is O(N^2). Where ‘N’ = the number of nodes in the linked list.
-
Space Complexity: Here the space complexity of the algorithm is O(N) as a separated sorted linked list is required to be prepared and then the heads of the list are exchanged.
Frequently Asked Questions
What do you mean by a singly linked list?
Here, by a ‘singly-linked list’ we use a linear unidirectional list data structure where each element in the list is known as a ‘node’ that can be traversed from the head of the list to the last node in the list and can be extended invariably.
What is the underlying approach that is utilized for performing insertion sort for the linked list here?
This problem uses an underlying approach of inserting nodes in a sorted linked list in a sorted manner with time complexity of O(N), where ‘N’ is the number of nodes in the list.
What is the time complexity of this approach?
The time complexity of this approach efficiently is O(N^2), where N is equal to the number of nodes in the singly list.
Conclusion
In this blog, we discussed the solution to the problem of performing insertion sort for a linked list.
We saw an implementation of insertion sort for linked lists in Python. Apart from this, you can practice more questions similar to this problem or on the insertion sort algorithm like Insertion sort for the linked list or other problems on linked lists and many more.
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Reading!