Linked lists are among the key topics that software engineers must master before going for a tech interview. Problems on linked lists are pretty popular in coding interviews.

In this article, we will cover a basic problem — how to use insertion sort on a singly linked list.

If you’re a software developer preparing for a technical interview, you would already know that the data structure “singly linked list” is quite similar to the array. The only difference is that data is not stored in a continuous manner in a singly linked list. All the elements are stored as “nodes,” and each node stores some data and pointers to the next node. 

The insertion sort is a sorting algorithm that works similar to how you sort playing cards in your hands. We use this algorithm to sort an array in O(n^2) complexity. 

Here’s what we’re going to cover in this article:

• Problem Statement
• Approach Used to Sort a Singly Linked List Using Insertion Sort 
• Pseudocode  for Sorting a Singly Linked List Using Insertion Sort 
• Code for Sorting a Singly Linked List Using Insertion Sort 
• Complexity of the Approach Used
• FAQs
  

Problem Statement 

You are given a singly linked list containing some finite number of nodes, and you have to sort it using insertion sort. Given a pointer pointing to the head node of the linked list, return the pointer to the new head after sorting the list. 

Example: 

Given list:

Output list:

Approach Used to Sort a Singly Linked List Using Insertion Sort 

To understand the approach, first, let’s do a quick review of how the insertion sort algorithm works. 

How is it implemented on an array? 

To implement insertion sort on the array, we need to iterate through the input array from left to right. For each element, we find the correct position to place it among the processed numbers.  

Let's see how it works using an example. Consider the array [8,3,4,1].

We first take the left-most element — there aren’t any elements to the left of 8; therefore, no change.

Next is 3. As 8>3, insert 3 before 8.

Then, we have 8>4 and 3<4 — insert 4 between 3 and 8.

In the next step, 3>1, 4>1, and 8>1, insert 1 before 3. 

We’re now at the last element, and our array is sorted.

Read the “Learn the Insertion Sort Algorithm” article for more details on how the insertion sort algorithm works
(includes pseudocode and code).

Now that we’ve covered how insertion sort works for arrays, let's see how we can implement it for the linked list. 

We can't access the element at a specific position directly in a singly linked list, unlike arrays. However, there is one aspect that we can replicate. While sorting an array using insertion sort, we maintained two subarrays:

• One with sorted elements 
• One with elements to be processed
  

For every node, we have the data stored in it and a pointer to the next node of it. 

Similarly, for the linked list, we can maintain two sets/linked lists:

• One with the sorted data (initially, it will be an empty linked list) 
• One with the unsorted/unprocessed data (initially, the whole input linked list will belong to this group)
  

We’ll iterate through the linked list from its head to tail. During this procedure, we will keep track of two pointers:

• “Sorted” will point to the minimum element of the sorted set (a linked list in our case)
• “Current” will point to the first element to be processed in the unsorted set (Initially, current will be equal to the head of the input linked list)
  

We will continue this process until our unsorted set becomes empty. Until that point, we will pick the node pointed by “current” and move it to the linked list pointed by “sorted.” Note that the nodes belonging to the linked list starting from “sorted” will always remain sorted (we will add nodes in this linked list keeping this invariant in mind). 

In the end, “sorted” will contain the sorted linked list.  

Algorithm for Sorting a Singly Linked List Using Insertion Sort 

Divide the given list into three groups: 

• A fixed sorted subset (the linked list starting with “sorted”)
• The current item (the node pointed by “current”)
• A subset containing remaining items (the linked list starting from the next node of “current”)
  

Subsets containing the remaining items will be processed in the subsequent iterations. 

Remember that, initially, “current” will point to the first item of the given list. While sorting the linked list with insertion sort, at each step, we have to follow the following steps: 

• Store the node that follows “current” in a variable and move the node pointed by “current” to the linked list starting from “sorted.” Technically, we are deleting a node from the unsorted collection and adding it to the sorted collection. 
• Find the correct location for the deleted item in the linked list starting with “sorted.” We can do this in the following way:

• Start from the beginning of the list, move on until we find the right position. 
• Once we’re done, we place that deleted item in there and proceed to the next step.

• Let “current” point to the stored node and repeat the above steps as long as “current” doesn’t point to null. 
  

Example of Applying Insertion Sort on a Singly Linked List

Let’s take the following as the input:

Step 1: We start with the first item, 5.

Step 2: Sorted set now has 5, and we remove the next item, 4, from the current list

Step 3: As 4<5, 4 is inserted before 5 in the sorted set

Step 4: 2<4, so place it before 4 in the sorted set

Step 5: 7>5, so it’s placed after 5 in the sorted set

Step 6: 1<2, so place it before 2

Step 7: 6>5 and 6<7, so place it after 5. The current list is empty, and our sorting is complete!

Pseudocode  for Sorting a Singly Linked List Using Insertion Sort 

function InsertionSort(Node head)
    Node sorted = NULL
    Node curr = head
    while curr != NULL
        Node currNext = curr.next
        SortedInsert(sorted ,curr)
        curr = currNext
    end while
    head = sorted 
end function

function SortedInsert(Node sorted, Node new_node)
    If sorted == NULL or sorted.data > new_node.data
        new_node.next = sorted 
        sorted = new_node
    end if
    else
        Node curr = sorted 
        while curr.next != NULL and curr.next.data <= new_node.data
            curr = curr.next
        end while
        new_node.next = curr.next
        curr.next = new_node
    end else
end function

Code for Sorting a Singly Linked List Using Insertion Sort

/*
* C++ Implementation for Insertion Sort on a Singly Linked List
*/
#include 
using namespace std;
/*
*ListNode is a data structure used to represents each node of our linked list
*/
struct ListNode
{
    int data;
    struct ListNode *next;
};

/* 
 It’s Implemented to insert data in the sorted list at the correct position
*/

void SortedPush(struct ListNode **head, struct ListNode *newListNode)
{
    // current node
    struct ListNode *curr;

    if (*head == NULL or (*head)->data > newListNode->data)
        newListNode->next = *head, *head = newListNode;
    else
    {
        // Need to locate the correct place to insert ListNode in the sorted linked list
        curr = *head;
        while (curr->next != NULL && curr->next->data <= newListNode->data)
            curr = curr->next;
        newListNode->next = curr->next, curr->next = newListNode;
    }
}

/*
* This is the driver function to sort the linked list using Insertion Sort
*/
void InsertionSort(struct ListNode **head)
{
    // Initialize sorted linked list as a NULL.
    // it is the set which we will keep sorted and insert the last processed node in it at every iteration.
    struct ListNode *sortedList = NULL;

    /* Travel given list and insert every node in sorted list at it's correct position */
    struct ListNode *curr = *head;
    while (curr != NULL)
    {
        // Store the next node of curr for next iteration
        struct ListNode *next = curr->next;
        // Inserting current in sorted linked list
        SortedPush(&sortedList, curr);
        // Updating current
        curr = next;
    }
    /* Update head to point to the sorted list */
    *head = sortedList;
}

/*
* Function to print the provided linked list 
*/
void PrintList(struct ListNode *head)
{
    struct ListNode *tp = head;
    while (tp != NULL)
    {
        cout << tp->data << " ";
        tp = tp->next;
    }
}

/*
* Function used to Push the node with a given in a linked list
*/
void Push(struct ListNode **last, struct ListNode **head, int data)
{
    // allocating new node
    struct ListNode *newListNode = new ListNode;

    // insert data in new node
    newListNode->data = data;
    newListNode->next = NULL;

    // inserting node at the end of list
    if (*head == NULL)
    {
        (*head) = newListNode;
        (*last) = (*head);
    }
    else
    {
        (*last)->next = newListNode;
        (*last) = newListNode;
    }
}

/*
* Main function 
*/
int main()
{
    // Creating a empty linked list to perform insertion sort on it
    struct ListNode *a = NULL, *last = a;

    // Interesting some nodes in it
    Push(&last, &a, 5);
    Push(&last, &a, 4);
    Push(&last, &a, 2);
    Push(&last, &a, 7);
    Push(&last, &a, 1);
    Push(&last, &a, 6);

    cout << "Linked List before sorting \n";
    PrintList(a);

    // performing insertion sort on given list
    InsertionSort(&a);

    cout << "\nLinked List after performing insertion sort \n";
    PrintList(a);
    return 0;
}

Complexity of the Approach Used

Let’s look at the time and space complexity of the approach we have used to sort a singly linked list using the insertion sort algorithm.

Time Complexity 

• Best case — O(n): Best-case input is a list that is already sorted. This type of input takes linear time to run.
• Worst case — O(n^2): Worst-case scenario occurs when the input array is reversely sorted. 
• Average case — O(n^2): The average-case complexity is also quadratic, making insertion sort slow for large inputs.
  

Space Complexity

Space complexity for all cases is O(1) — for each iteration, we only use constant pointers and variables. Note that we did not create new nodes. Instead, we moved the already existing nodes. 

Advantages and Disadvantages of Using Insertion Sort for Sorting a Singly Linked List 

Advantages:

1. Insertion sort on a list uses very little additional space.
2. It is one of the best algorithms for sorting when the size of input data is small.
3. We can effectively use this algorithm to maintain a dynamic sorted dataset of small size or when we do not have all the input initially. 
4. It is a stable sorting algorithm as it preserves the relative order of any two equal elements. 
5. Comparably easy to code. 
   

Disadvantages:

1. Compared to other sorting algorithms, insertion sort is slower for large-sized input data. 
   
   

FAQs on Insertion Sort for Sorting a Singly Linked List    

Question 1: Where can we use insertion sort for sorting a singly linked list? 

Generally, insertion sort is used when the size of the list is small. Also, in such cases where only a few elements are misplaced in the list, it is more efficient than other practical sorting algorithms like selection sort and bubble sort. 

Question 2:  Is insertion sort on linked list faster than on array? 

No. In the worst case, it will take an asymptotically quadratic number of operations. 

The shifting is done in the same way as searching for a place to be inserted. Using the linked list instead of an array will eliminate the shifting, but we’ll still need to search for the position.  

Hence, its average- and worst-case complexity will be quadratic, and best-case complexity will be linear.

‍

Are You Ready to Nail Your Next Coding Interview?

If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

‍
--------

Article contributed by Omkar Deshmukh