Insert Node in the Sorted Linked List

Insert Node in the Sorted Linked List” is one of the popular programming problem based on Linked List data structure. Here, we are given a sorted linked list and our task is to insert a node in a sorted linked list in such a way that after inserting the new node the linked list remains sorted.

Example:

Suppose we need to insert a node with value ‘17’ in a following linked list:
LINKED LIST:       
12 -> 13 -> 16 -> 19 -> 23
After Inserting in the sorted manner the linked list would be as follows:
LINKED LIST:       
12 -> 13 -> 16 -> 17 -> 19 -> 23

The steps required to insert node in the sorted linked list are as follows:

  1. If the linked list is empty, then the new_node will become head of the linked list.
  2. Else, if the new_node value is smaller than or equal to the head node value, then point the pointer of new_node to the head of the linked list and make head of the resultant linked list to the new_node of the list.
  3. Else, traverse the linked list till we get the node value greater than or equal to the new_node value.
  4. Then, insert the new_node at the desired location after manipulating pointers of the linked list.

C++ Program to insert node in the sorted linked list is as follows:

/* C++ Program to Insert Node in the Sorted Linked List */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the Linked List */
typedef struct node
{
    int data;
    struct node *next;
}Node;

/* Function to Insert Node at the Sorted Linked List */
void sortedInsert(Node **head, int ele)
{
    /* Creating New Node */
    Node *new_node = (struct node*)malloc(sizeof(struct node));
    new_node -> data = ele;
    new_node -> next = NULL;
    
    /* Check whether Linked List is Empty or Not */
    
    /* If Linked List is Empty, then new node will become head of the Linked List */
    if((*head) == NULL)
    {
        (*head) = new_node;
        return;
    }
    
    /* If Linked List is not empty, 
        1. If New Node Value is smaller or equal to Head Node Value,
           then, insert new node at the beginning of the linked List
           and head will become the new node of the linked list.
           
        2. Else, traverse the linked list, till we get the node value 
           greater than or equal to the new node value. Then, insert the 
           new node at the desired location after manipulating pointers of 
           the linked list.
    */
    struct node *temp = (*head);
    if(ele <= (*head)->data)
    {
        new_node -> next = (*head);
        (*head) = new_node;
        return;
    }
    while(temp->next!= NULL && temp->next->data < ele)
    {
        temp = temp -> next;
    }
    new_node -> next = temp -> next;
    temp -> next = new_node;
}

/* Function to print the Linked List */
void print(Node *head)
{
    Node *temp = head;
    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->next;
    }
    cout<<endl;
}
int main()
{
    Node *head = NULL;
    /* Inserting Some Nodes in a sorted Linked List */
    sortedInsert(&head,12);
    sortedInsert(&head,13);
    sortedInsert(&head,10);
    sortedInsert(&head,15);
    sortedInsert(&head,18);
    sortedInsert(&head,5);
    cout<<"The Elemens of the Linked List: \n";
    print(head);
}
OUTPUT:
The Elemens of the Linked List:
5 10 12 13 15 18

Related Posts:

  1. Insert a New Node at the beginning of the Linked List.
  2. Insert a New Node at the end of the Linked List.
  3. Insert a New Node at the Middle of the Linked List.
  4. Reverse a Linked List.
  5. Reverse a Linked List Using Stack.
  6. Printing Linked List in Reverse Order without actually reversing the Linked List.
  7. Swap Adjacent Elements of the Linked List.
  8. Count All Occurrences of a Particular Node in a Linked List.
  9. Bubble Sort on Linked List.
  10. Detect a Loop in a Linked List.
  11. Find the Length of the Loop present in the Linked List.
  12. Detect and Remove Loop from a Linked List.
  13. Segregate Even and Odd Nodes of the Linked List.
  14. Delete Complete Linked List.
  15. Delete Nth Node of the Linked List.
  16. Delete without head pointer of the Linked List.
  17. Delete All Occurrences of particular node of the Linked List.
  18. Delete Alternate Nodes of the Linked List.
  19. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  20. Find Union and Intersection of Two Linked List.

You may also like...