Interview Kickstart has enabled over 3500 engineers to uplevel.
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:
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.
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:
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:
We’ll iterate through the linked list from its head to tail. During this procedure, we will keep track of two pointers:
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.
Divide the given list into three groups:
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:
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!
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.
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.
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