Which of the following sorting algorithm we can use to sort a linked list keeping the time complexity in mind?

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