Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

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:

- 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

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:

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.

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.

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.

**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 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:**

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

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

Oops! Something went wrong while submitting the form.