C Program to Insert an element in a Sorted Linked List

Insertion of an element in a Sorted Linked List

C Program to Insert an element in a Sorted Linked List.We know that a single element is always sorted, in this we have to sort the elements and then insert the element in the sorted linked list.It is just like an element insertion in the sorted array which is quite easy to implement in the data structures.
For Example:-
Input:- 4–>20–>10–>41–>25–>30
Element to be inserted:- 55
Output:- 4–>10–>20–>25–>30–>41–>55
In this article we will discuss in detail in C Programming Language.

Insertion in a Sorted Linked List using C
C Code to Insert an element in a Sorted Linked List

Implementation for inserting an element in a Sorted Linked List:-

STEP 1:- When Linked list is empty then make the node as head and return it to the linked list.

STEP 2:- When data or value of the node to be inserted is smaller than the value of head node, then insert the node at the start and make it head of the linked list.

STEP 3:- Make operations to find the correct node after which the input node is to be inserted in the linked list.

STEP 4:- To find the correct node start from head, keep traversing until we reach a node whose value is larger or greater than the input node. The node just before the node is the correct node.

STEP 5:- Lets insert the node after the correct node as we done in Step 4.

How to Make node in the linked list is as follows:-

struct node
{
int data;
struct node *next;
};

C Program to insert an element in a Sorted Linked List:-

#include <stdio.h>
#include <stdlib.h>
struct node
{
	int data;
	struct node* next;
};

void list(struct node** head, int data)//function to build linked list
{
	struct node* newNode = (struct node*)malloc(sizeof(struct node));
	newNode->data = data;
	newNode->next = *head;
	*head = newNode;
}
void display(struct node* head)//function to print linked list
{
	struct node* ptr = head;
	while (ptr)
	{
	     printf("%d  ",ptr->data);
		ptr = ptr->next;
	}
}

struct node* newNode(int data)
{
	struct node* newNode = (struct node*)malloc(sizeof(struct node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

void insertion_sort(struct node** head, struct node* newNode)//function to insert data in sorted position
{
	//If linked list is empty
	if (*head == NULL || (*head)->data >= newNode->data)
	{
		newNode->next = *head;
		*head = newNode;
		return;
	}

	//Locate the node before insertion
	struct node* current = *head;
	while (current->next != NULL && current->next->data < newNode->data)
		current = current->next;

	newNode->next = current->next;
	current->next = newNode;
}

int main(void)//main method
{
    int n,k;
	printf("Enter the size of linked list :\n");
	scanf("%d",&n);
	int data[100];
	printf("Enter linked list data in sorted order :\n");
	for(int i=0;i<n;i++)
	{
	    scanf("%d",&data[i]);
	}
	
	struct node* head = NULL;
    
	//constructing linked list
	for (int i = n-1; i >= 0; i--)
	list(&head, data[i]);
	printf("Linked list before insertion : \n");
    display(head);
    printf("\nEnter data you want to insert: ");
    scanf("%d",&k);
	insertion_sort(&head, newNode(k));
	printf("Linked list after insertion : ");
	display(head);

	return 0;
}
Output:-
Enter the size of linked list :
5
Enter linked list data in sorted order :
11
15
41
48
56
Linked list before insertion : 
11  15  41  48  56
Enter data you want to insert: 25
Linked list after insertion : 
11  15  25  41  48  56

To learn more about data structures click on the button below:-