C Program to Insert an element in a Sorted Linked List

March 20, 2025

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

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.

C Program to Insert an element in a Sorted Linked List

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

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

Delete alternate nodes of a Linked List

Find middle of the linked list

Reverse a linked list in groups of given size

Find kth node from end of the linked list

Append the last n nodes of a linked list to the beginning of the list

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;
}

//function to insert data in sorted position
void insertion_sort (struct Node **head, struct Node *newNode)	
{
  //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

 

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.

Asked in the following exams/interviews