Write a program to insert a node in a sorted Linked List

Question:

Write a program to insert a node in a given sorted Linked List.

Given List: 23 -> 32 -> 99 -> 101 -> 2222
Node to add:- 50

Output:- 23 -> 32 -> 50 -> 99 -> 101 -> 2222

To insert a node in a sorted Linked List, we need to perform a basic Linked List operation discussed in this post.

• Insert a node in a Linked List.

In the given post, we knew the position at which we had to insert the node. But in this case we need to find the position at which we have to insert the node.

To find the position, start traversing the list from the beginning and get to the point, where we need to insert the node. Then we can call the insert a node function.

We can implement this problem this way.

#include

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

//defining a function to insert in sorted list
struct node * insertInSorted(struct node * head, int number)
{
	//let us suppose the initial position to be zero
	int pos = 0;

	//always create a temporary variable as we should never loose
	//the List HEAD
	struct node * temp = head;

	//now we need to traverse the list until we reach the node whose value
	//is greater than the number input.
	//If the 3rd number is greater, that means we need to insert a new number
	//at the third position.
	while(temp != NULL)
	{
		if(temp->data > number)
			break;    // if we get the node, means we have the position, break

		temp = temp->next;  // the next node
		pos++;  // increment the position
	}

	head = addAtPos(head, number, pos);  // we can call our original made function

	return head;
}

//helper functions
struct node * addAtPos(struct node *head, int number, int pos)
{
    int initial_pos = 0;
    struct node * mover = head;

    while(initial_pos != pos)
    {
        mover = mover -> next;
        initial_pos++;
    }

    struct node * temp = (struct node*)malloc(sizeof(struct node));
    temp -> data = number;

    temp -> next = mover -> next;
    mover -> next = temp;

    return head;
}

struct node * addElement(struct node *head, int number)
{
	struct node * temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = number;
	temp -> next = NULL;

	struct node * temp2 = head;

	while(temp2 -> next != NULL)
	{
		temp2 = temp2 -> next;
	}

	temp2 -> next = temp;

	return head;
}

void printList(struct node * head)
{
	while(head != NULL)
	{
		printf("%d ",head->data);
		head = head->next;
	}
}

//main function to test the code
int main(void)
{
	//creating a list with initial sorted elements
	struct node * listHead = (struct node*)malloc(sizeof(struct node));
	listHead->data = 23;
	listHead->next = NULL;
	listHead = addElement(listHead, 32);
	listHead = addElement(listHead, 99);
	listHead = addElement(listHead, 101);
	listHead = addElement(listHead, 2222);

	printf("Enter a number to insert in sorted list:- ");
	int num;
	scanf("%d",&num);

	listHead = insertInSorted(listHead, num);

	printList(listHead);

	return 0;
}

Enter a number to insert in sorted list:- 50
23  32  50  99  101  2222