 New update is available. Click here to update.
Last Updated: Feb 5, 2023

# Insertion Sort for Singly Linked List Author dhruv sharma 0 upvotes

## Introduction

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.

Also see, Data Structures

## Problem Statement

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.

For example:

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.

## 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.

1. 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.
2. 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.
3. 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).
4. 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.

1. The first step will be to create an empty sorted linked list with a head referring to a null node.
2. 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.
1. I.e. Inserting a node in a sorted linked list in a sorted way. (the same algorithm  that was introduced above is repeated here)
3. 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.

### 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.

sorted = None

# Traverse the given linked list and insert every node to sorted.
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

# Function to insert a new_node in a list.
# Note that this function expects a pointer to head_ref as this can modify the

current = None

# Special case for the head end.

else:

# Locate the node before the point of insertion.
while (current.next != None and
current.next.data < new_node.data):

current = current.next

new_node.next = current.next
current.next = new_node

# Function to print linked list.

while(temp != None):

print( temp.data, end = " ")
temp = temp.next

# A utility function to insert a node at the beginning of linked list.

# Allocate node.
new_node = Node(0)

# Put in the data.
new_node.data = new_data

# Link the old list off the new node.

# Move the head to point to the new node.

# 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)

printList(a)
a = insertionSort(a)

printList(a)

``````

Output

``````Linked List before insertion sort:
3 1 6 4 2 5
1 2 3 4 5 6
``````

### 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.

### 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. Go on top