# C/C++ Program to add a node to an ascending order linked list

Write a program to add a node to an ascending order linked list in C/C++. In simple words, we need to insert data in a sorted linked list such that the linked list remains sorted even after the insertion of a new node.

Example,

```If the current linked list is
9 -> 12 -> 14 -> 19 -> 35 -> NULL

Insert 15 to the linked list
9 -> 12 -> 14 -> 15 -> 19 -> 35 -> NULL

The linked list is in ascending order even after inserting 15.```

We have divide the problem is 2 parts

1. Case 1
In this case, the value of the new node is less than the value of the first node. We simply insert a new node at the beginning of the linked list.
2. Case 2
In this case, the value of the new node is greater than the value of the first node. We iterate each element of the linked list and find a node ptr whose value is just less than the value of the new node. We then insert the new node immediately after ptr.

See the code for more details.

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

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

// function to display linked list
void displayll(struct node *root){
struct node *temp = root;
while(temp!=NULL){
printf("%d -> ",temp->val);
temp = temp->next;
}
printf("NULL\n\n");
}

// Function to insert a new value - val into linked list head.
// The value - val is inserted in the linked list such that
// the resultant linked list is also sorted
struct node* insert_sortedll(node *head, int val){

struct node *ptr;
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->val = val;
temp->next = NULL;

// this section runs if linked list is empty
// we simply set head to temp
}
// this section runs if the new val is smaller then
// the first value in the linked list
// we simple insert temp at the beginning of the linked list
}
else{
// we are iterating each element of the linked list
// to find the node whose value is just smaller than val
while(ptr->next!=NULL&&ptr->next->val<temp->val){
ptr = ptr->next;
}
// ptr now points to the node whose value is just less than val
// we simply insert temp between ptr and ptr->next
temp->next = ptr->next;
ptr->next = temp;
}

}

int main() {

printf("Insert 8 into the LinkedList !!!\n");
printf("Insert 4 into the LinkedList !!!\n");
printf("Insert 12 into the LinkedList !!!\n");

printf("Insert 1 into the LinkedList !!!\n");
printf("Insert 3 into the LinkedList !!!\n");
printf("Insert 10 into the LinkedList !!!\n");

}
``````

Output

``````Insert 8 into the LinkedList !!!
Insert 4 into the LinkedList !!!
Insert 12 into the LinkedList !!!

LinkedList: 4 -> 8 -> 12 -> NULL

Insert 1 into the LinkedList !!!
Insert 3 into the LinkedList !!!
Insert 10 into the LinkedList !!!

LinkedList: 1 -> 3 -> 4 -> 8 -> 10 -> 12 -> NULL``````