Insertion Sort for Singly Linked List

Given a linked list, write a function that will sort the linked list using Insertion Sort.

Example

INPUT :
23 ->1 ->50 ->15 ->16 ->6

OUTPUT :
1 ->6 ->15 ->16 ->23 ->50

Time Complexity : O()

Algorithm

1. Create a list "result" to store the sorted list

2. Traverse the given list
    a. Insert current node in sorted way in result list

3. Print the result list

The above Algorithm can be clearly explained in below diagram

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
	int data;
	LLNode *next;	
};
// Prototype
void sortedInsert(LLNode**, LLNode*);
 
// function to sort a singly linked list using insertion sort
LLNode* insertionSort(LLNode **head)
{
    // Initialize result linked list
    LLNode *result = NULL;
 
    // Traverse the given list
    LLNode *curr = *head;
    while (curr != NULL)
    {
        // Store next for next iteration
        LLNode *next = curr->next;
 
        // insert current in result linked list
        sortedInsert(&result, curr);
 
        // Update current
        curr = next;
    }
 
    // return the result list
    return result;
}
 
 
//Insering the node in correct position in result list
void sortedInsert(LLNode** result, LLNode* new_Node)
{
    LLNode* temp;
    //If there is no element in result list
    if (*result == NULL || (*result)->data >= new_Node->data)
    {
        new_Node->next = *result;
        *result = new_Node;
    }
    else
    {
        //finding the position to insert the node
        temp = *result;
        while (temp->next!=NULL && temp->next->data < new_Node->data)
        {
            temp = temp->next;
        }
        new_Node->next = temp->next;
        temp->next = new_Node;
    }
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node with this data and next pointing to NULL
	curr->data=dataToBeInserted;
	curr->next=NULL;

	if(*head==NULL) //if list is empty then set the current formed node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	while(temp!=NULL) //till the list ends (NULL marks ending of list)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}

int main() 
{    
	
	LLNode *head = NULL; //initial list has no elements
	LLNode* result = NULL;

	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);

	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	result = insertionSort(&head);
	cout<<"After doing insertion sort"<<endl;
	display(&result);
	return 0;
}
Try It

 

 


Next > < Prev
Scroll to Top