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

Leave a Comment

Your email address will not be published. Required fields are marked *