Insert an Element in a Sorted Linked List

Inserting in a sorted linked list means that the linked list will remain sorted after the insertion. So to insert a new element, we need to find out the appropriate place and insert the new node there.

Logic to Insert an Element in a Sorted Linked List

1. If head points to NULL or the new value (to be inserted) is less the value of first node, insert the new node at the front of the list.
2. Else, traverse the list (tmp_node is the current node) and find the appropriate place to insert.
   1. If the current node is the last node or the new value is less than the value of the next node (tmp_node->next->val), insert the new node after the current node.
   2. Else move to the next node.

The Program

#include <stdio.h>
#include <stdlib.h>

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

void print_list(struct node *head)
{
    printf("H->");

    while(head)
    {
        printf("%d->", head->val);
        head = head->next;
    }

    printf("|||\n");
}

void insert_sorted(struct node **head, int value)
{
    struct node * new_node = NULL;
    struct node * tmp_node = NULL;

    new_node = (struct node *)malloc(sizeof(struct node));

    if (new_node == NULL)
    {
        printf("Failed to insert element. Out of memory");
    }

    new_node->val = value;

    if(*head == NULL || value < (*head)->val)
    {
        new_node->next = *head;
        *head = new_node;
        return;
    }

    tmp_node = *head;

    while(tmp_node->next && value > tmp_node->next->val)
    {
        tmp_node = tmp_node->next;
    }

    new_node->next = tmp_node->next;
    tmp_node->next = new_node;
}

void main()
{
    int count = 0, i, val;
    struct node * head = NULL;

    printf("Enter number of elements: ");
    scanf("%d", &count);

    for (i = 0; i < count; i++)
    {
        printf("Enter %dth element: ", i);
        scanf("%d", &val);
        insert_sorted(&head, val);
    }

    printf("List after insertion: ");
    print_list(head);
}

Here is the output of the program.

Enter number of elements: 10
Enter 0th element: 6
Enter 1th element: 34
Enter 2th element: 5
Enter 3th element: 90
Enter 4th element: 65
Enter 5th element: 78
Enter 6th element: 65
Enter 7th element: 34
Enter 8th element: 23
Enter 9th element: 88
List after insertion: H->5->6->23->34->34->65->65->78->88->90->|||

We kept inserting the integers in a random order but the final list became sorted. Because at particular moment the list is sorted and the list remains sorted after every insertion.

Read also: Insert an element in a linked list at various places.

If you also want to contribute, click here.