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

Run
// Linked List in C Implementation code
#include<stdio.h>
#include<stdlib.h>
//stdlib is included because we will be using  ‘malloc’

// creating a node in linked list
struct Node { 
    int data; 
    struct Node* next; 
    // Pointer pointing towards next node
};

//function to print the linked list
void display(struct Node* node) 
{ 
    while (node != NULL) { 
        printf("%d ", node->data); 
        node = node->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;
}

// main function
int main() 
{
    int k;
    //creating 4 pointers of type struct Node
    //So these can point to address of struct type variable
    struct Node* head = NULL;
    struct Node* node2 = NULL;
    struct Node* node3 = NULL;

    // allocate 3 nodes in the heap
    head =  (struct Node*)malloc(sizeof(struct Node));
    node2 = (struct Node*)malloc(sizeof(struct Node));
    node3 = (struct Node*)malloc(sizeof(struct Node));

   
    head->data = 10; // data set for head node 
    head->next = node2; // next pointer assigned to address of node2 

    node2->data = 15;
    node2->next = node3;

    node3->data = 20;
    node3->next = NULL;

    printf("Linked list before insertion : ");
    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

Linked list before insertion : 10 15 20 
Enter data you want to insert: 18
Linked list after insertion : 10 15 18 20

 

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

Quiz time

Quiz Time

Question 1. Write a function to insert a number into a sorted linked list. assume the list is sorted from smallest to largest value. after insertion, the list should still be sorted. given the list l1 = (3, 17, 18, 27) and the value 20, on return l1 be the list (3, 17, 18, 20, 27)

Take inspiration from the above code.