Register for our webinar

How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings

Using Insertion Sort on a Singly Linked List

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.

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

• 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 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

``````
Node sorted = NULL
while curr != NULL
Node currNext = curr.next
SortedInsert(sorted ,curr)
curr = currNext
end while
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;

else
{
// Need to locate the correct place to insert ListNode in the sorted linked list
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
*/
{
// 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 */
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 */
}

/*
* Function to print the provided linked list
*/
{
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
{
}
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.

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.

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.

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!

--------

Article contributed by Omkar Deshmukh

Last updated on:
October 27, 2023

Engineering Manager at Interview Kickstart