Insertion Sort for Singly Linked List
This problem is asked in one of the top FAANG companies. If you are aiming for such companies, then this problem is a must-do.
For this problem, we need to understand how can a node be inserted in a sorted way in a given sorted list of nodes
Let us understand it using a problem statement and a few examples.
Suppose you are given the ‘head’ of a singly linked list. It is required of us to sort the list using the Insertion Sort technique and finally return the ‘head’ of the linked list that is now sorted. Our main aim here is to design an algorithm by which all the nodes of the singly linked list can be sorted using insertion sort.
The following example given below is a graphical example of the insertion sort algorithm. Here, the partially sorted list (in black) initially contains only the first element in the list. One element (green) is removed from the input data and inserted in place into the sorted list with each iteration.
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 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, 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 the 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.
# 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)
Linked List before insertion sort: 3 1 6 4 2 5 Linked List after insertion sort: 1 2 3 4 5 6
- 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
1). 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.
2). What is the underlying approach that is utilised for performing insertion sort for linked list here?
This problem uses an underlying approach of inserting nodes in a sorted linked list in a sorted manner with a time complexity of O(N), where ‘N’ is the number of nodes in the list.
3). 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.
In this blog, we discussed the solution for the problem of performing insertion sort for 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 linked list or other problems on linked lists and many more.
You can also have a view of the Data Structures and Algorithms guided path to start your preparation from scratch.