Insertion Sort for Singly Linked List

In this article, we will discuss how to perform insertion sort using linked list. The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The elements are virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a singly linked list, and we need to sort the given list using the insertion sort technique.

Input:

Output:

Explanation: The given list has been sorted.

This question is not a tricky one. Let’s start performing insertion sort in linked list.

Let us have a glance at the approach.

Approach for Performing Insertion Sort In Linked List

The approach is going to be pretty simple.

  • We will create an empty result singly linked list, which will be sorted.
  • Then, we will traverse the given linked list, and for every node that we visit, we will insert the current node in a sorted way in our result list.
  • To insert in a sorted way:
    • We will traverse our result list and keep comparing every node with our current node.
    • As soon as we find a node whose value is greater than the current node, we will insert the current node just before that node.
    • If the current node value is greater than every other node of our result list, then we will append the current node at the end.
    • To see the above process of inserting an element in a sorted list in a sorted way in more detail, check out the article link provided above in the above section.
  • After complete traversal, change the head of the given linked list to the head of the result list.
  • Finally, return the head.

Let’s move to the algorithm to see the approach in more depth.

Algorithm For Performing Insertion Sort Using Linked List

  • Initialize the newly created sorted list as NULL.
  • Traverse the given singly linked list using a pointer say current.
    • For every node, while traversal, store the next of node in a temp variable and remove all of its links.
    • Insert the current node in a sorted way in the result list.
    • Update current’s value with temp for further traversal.
  • Once the traversal is over, update the head pointer by making it point to our result list.
  • Return the head pointer.

Dry Run For Performing Insertion Sort on Linked List

Code Implementation For Performing Insertion Sort in Linked List

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node* next;
};
 
struct node* head = NULL;
struct node* sorted = NULL;
 
void push(int val)
{
    /* allocate node */
    struct node* newnode
        = (struct node*)malloc(sizeof(struct node));
    newnode->data = val;
    /* link the old list off the new node */
    newnode->next = head;
    /* move the head to point to the new node */
    head = newnode;
}
void sortedInsert(struct node* newnode)
{
    /* Special case for the head end */
    if (sorted == NULL || sorted->data >= newnode->data) {
        newnode->next = sorted;
        sorted = newnode;
    }
    else {
        struct node* current = sorted;
        /* Locate the node before the point of insertion
         */
        while (current->next != NULL
               && current->next->data < newnode->data) {
            current = current->next;
        }
        newnode->next = current->next;
        current->next = newnode;
    }
}
 
// function to sort a singly linked list
// using insertion sort
void insertionsort()
{
 
    struct node* current = head;
 
    // Traverse the given linked list and insert every
    // node to sorted
    while (current != NULL) {
 
        // Store next for next iteration
        struct node* next = current->next;
 
        // insert current in sorted linked list
        sortedInsert(current);
 
        // Update current
        current = next;
    }
    // Update head to point to sorted linked list
    head = sorted;
}
 
/* Function to print linked list */
void printlist(struct node* head)
{
    while (head != NULL) {
        printf("%d->", head->data);
        head = head->next;
    }
    printf("NULL");
}
 
// Driver program to test above functions
int main()
{
 
    push(5);
    push(20);
    push(4);
    push(3);
    push(30);
 
    printf("Linked List before sorting:\n");
    printlist(head);
    printf("\n");
 
    insertionsort(head);
 
    printf("Linked List after sorting:\n");
    printlist(head);
}
#include <bits stdc++.h="">
using namespace std;
 
struct Node {
    int val;
    struct Node* next;
    Node(int x)
    {
        val = x;
        next = NULL;
    }
};
 
class LinkedlistIS {
 
public:
    Node* head;
    Node* newhead;
 
    void push(int val)
    {

        Node* newnode = new Node(val);

        newnode->next = head;
 
        head = newnode;
    }
 
    void insertionSort(Node* headref)
    {
        newhead = NULL;
        Node* current = headref;

        while (current != NULL) {

            Node* temp = current->next;

            sortedInsert(current);
            // Update current
            current = temp;
        }

        head = newhead;
    }
    
    void sortedInsert(Node* newnode)
    {

        if (newhead == NULL || newhead->val >= newnode->val) {
            newnode->next = newhead;
            newhead = newnode;
        }
        else {
            Node* current = newhead;
 
            while (current->next != NULL
                   && current->next->val < newnode->val) {
                current = current->next;
            }
            newnode->next = current->next;
            current->next = newnode;
        }
    }

    void printlist(Node* head)
    {
        while (head != NULL) {
            cout << head->val << " ";
            head = head->next;
        }
    }
};
int main()
{
    LinkedlistIS list;
    list.head = NULL;

    list.push(3);
    list.push(1);
    list.push(2);
    list.push(4);
    list.push(5);
    cout << "Linked List before sorting" << endl;
    list.printlist(list.head);
    cout << endl;
    list.insertionSort(list.head);
    cout << "Sorted Linked List" << endl;
    list.printlist(list.head);
}
public class LinkedlistIS
{
    node head;
    node newhead;
 
    class node
    {
        int val;
        node next;
 
        public node(int val)
        {
            this.val = val;
        }
    }
 
    void push(int val)
    {

        node newnode = new node(val);

        newnode.next = head;

        head = newnode;
    }

    void insertionSort(node headref)
    {
 
        newhead = null;
        node current = headref;

        while (current != null)
        {

            node temp = current.next;

            sortedInsert(current);

            current = temp;
        }

        head = newhead;
    }

    void sortedInsert(node newnode)
    {

        if (newhead == null || newhead.val >= newnode.val)
        {
            newnode.next = newhead;
            newhead = newnode;
        }
        else
        {
            node current = newhead;

            while (current.next != null && current.next.val < newnode.val)
            {
                current = current.next;
            }
            newnode.next = current.next;
            current.next = newnode;
        }
    }

    void printlist(node head)
    {
        while (head != null)
        {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
     

    public static void main(String[] args)
    {
        LinkedlistIS list = new LinkedlistIS();

        list.push(3);
        list.push(1);
        list.push(2);
        list.push(4);
        list.push(5);
        System.out.println("Linked List before Sorting..");
        list.printlist(list.head);
        list.insertionSort(list.head);
        System.out.println("\nSorted Linked List");
        list.printlist(list.head);
    }
}
class Node:
    
    def __init__(self, data):
        self.data = data
        self.next = None

def insertionSort(head_ref):

    sorted = None
    current = head_ref
    while (current != None):
    
        next = current.next
        sorted = sortedInsert(sorted, current)
        current = next
    
    head_ref = sorted
    return head_ref

def sortedInsert(head_ref, new_node):

    current = None

    if (head_ref == None or (head_ref).data >= new_node.data):
    
        new_node.next = head_ref
        head_ref = new_node
    
    else:
    
        current = head_ref
        while (current.next != None and
            current.next.data < new_node.data):
        
            current = current.next
        
        new_node.next = current.next
        current.next = new_node
        
    return head_ref


def printList(head):

    temp = head
    while(temp != None):
    
        print( temp.data, end = " ")
        temp = temp.next
    
def push( head_ref, new_data):

    new_node = Node(0)
    new_node.data = new_data
    new_node.next = (head_ref)
    (head_ref) = new_node
    return head_ref


a = None
a = push(a, 3)
a = push(a, 1)
a = push(a, 2)
a = push(a, 4)
a = push(a, 5)

print("Linked List before sorting ")
printList(a)

a = insertionSort(a)

print("\nLinked List after sorting ")
printList(a)

Output

Linked List before Sorting.
5 4 2 1 3
Sorted Linked List
1 2 3 4 5

Time Complexity For Performing Insertion Sort using Linked List: O(n2), as we are using nested traversal

With the help of this article, we have tried to explain the most efficient approach to perform insertion sort in linked list. Insertion sort is an important technique, and when it gets coupled with a singly linked list, it becomes even more important. If you want to solve more questions on Linked List, which our expert mentors at PrepBytes curate, you can follow this link Linked List.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQ Related to Insertion Sort Using Linked List

  1. What is insertion sort?
  2. Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part.

  3. Why insertion is faster in the linked list?
  4. A LinkedList consumes a bit more memory than an ArrayList since every node stores two references to the previous and next elements. The insertion, addition, and removal operations are faster in a LinkedList because there is no resizing of an array done in the background.

  5. What are the 4 types of a linked list?
  6. There are four key types of linked lists:

    • Singly-linked>Singly-linked lists.
    • Doubly linked lists.
    • Circular linked lists.
    • Circular doubly linked lists.

Leave a Reply

Your email address will not be published. Required fields are marked *