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" else="" end="" function="" <="" code="">
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:
Insertion sort on a list uses very little additional space.
It is one of the best algorithms for sorting when the size of input data is small.
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.
It is a stable sorting algorithm as it preserves the relative order of any two equal elements.
Comparably easy to code.
Disadvantages:
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!
.png)
