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
- 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. - 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;
printf("\nLinkedList: ");
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;
if(head==NULL){
// this section runs if linked list is empty
// we simply set head to temp
head = temp;
}
else if(temp->val <= head->val){
// 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
temp->next = head;
head = temp;
}
else{
// we are iterating each element of the linked list
// to find the node whose value is just smaller than val
ptr = head;
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;
}
return head;
}
int main() {
struct node *head = NULL;
printf("Insert 8 into the LinkedList !!!\n");
head = insert_sortedll(head, 8);
printf("Insert 4 into the LinkedList !!!\n");
head = insert_sortedll(head, 4);
printf("Insert 12 into the LinkedList !!!\n");
head = insert_sortedll(head, 12);
displayll(head);
printf("Insert 1 into the LinkedList !!!\n");
head = insert_sortedll(head, 1);
printf("Insert 3 into the LinkedList !!!\n");
head = insert_sortedll(head, 3);
printf("Insert 10 into the LinkedList !!!\n");
head = insert_sortedll(head, 10);
displayll(head);
}
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