C++ program for insertion in a Sorted Linked List

June 30, 2020

Program for insertion in a sorted linked list in C++

How to insert data in a sorted linked list?

In the following article, we will learn to write a C++ program for insertion in a sorted linked list with a condition that list input by user is already sorted. If the list is unsorted then first we need to sort the linked list and later we can perform the steps and algorithm mentioned below. Insertion in a linked can simple be perform in 3 different manners -:

  • Insertion at Beginning
  • Insertion at end
  • Insertion at nth position

This article is almost similar as to insertion at nth position, we will be using the same logic the only main difference is that we will be working on a sorted linked list, so the position of the element will be decided after comparing it with all the smaller elements of the linked list.

Steps to write a C++ program for insertion in a sorted linked list

S

T

E

P

S

To insert a node in a sorted linked list in C++ following steps are followed

  1. Define the linked list.
  2. In the main method call all the method you have declared with input/output statement you want to use.
  3. Function named build is used to build the linked list.
  4. Print will be used to display the list.
  5. newNode will construct new node for insertion.
  6. Now in our function named sortedInsert core process of the program take place.
  7. First if the list is empty or data at previous head is greater then the data we are inserting, we will insert new node as head in the list.
  8. Else we will traverse through the linked list and insert new node at the required position.

S

T

E

P

S

To insert a node in a sorted linked list in C++ following steps are followed

  1. Define the linked list.
  2. In the main method call all the method you have declared with input/output statement you want to use.
  3. Function named build is used to build the linked list.
  4. Print will be used to display the list.
  5. newNode will construct new node for insertion.
  6. Now in our function named sortedInsert core process of the program take place.
  7. First if the list is empty or data at previous head is greater then the data we are inserting, we will insert new node as head in the list.
  8. Else we will traverse through the linked list and insert new node at the required position.

How to construct a linked list ?

Syntax 

class Node  
{  
    int data;  
    Node *next;  
}; 

Using following set of codes in our program we can construct linked list.

C++ program for insertion in a sorted linked list

Algorithm for insertion in a sorted linked list in C++

A

L

G

O

R

I

T

H

M

  1. IF (*HEAD==NULL || (*HEAD)->DATA>=NEWNODE->DATA
  2. NEWNODE->NEXT=*HEAD
  3. *HEAD=NEWNODE
  4. RETURN AND END IF
  5. WHILE(CURRENT->NEXT!=NULL && CURRENT->NEXT->DATADATA)
  6. CURRENT=CURRENT->NEXT
  7. NEWNODE->NEXT=CURRENT->NEXT
  8. CURRENT->NEXT=NEWNODE

A

L

G

O

R

I

T

H

M

  1. IF (*HEAD==NULL || (*HEAD)->DATA>=NEWNODE->DATA
  2. NEWNODE->NEXT=*HEAD
  3. *HEAD=NEWNODE
  4. RETURN AND END IF
  5. WHILE(CURRENT->NEXT!=NULL && CURRENT->NEXT->DATADATA)
  6. CURRENT=CURRENT->NEXT
  7. NEWNODE->NEXT=CURRENT->NEXT
  8. CURRENT->NEXT=NEWNODE

Program for insertion in a sorted linked list in C++

#include <iostream>
using namespace std;

struct node
{
	int data;
	struct node* next;
};
void build(struct node** head, int data);
void print(struct node* head);
void sortedInsert(struct node** head, struct node* newNode);
struct node* newNode(int data);

int main(void)//main method.
{
    int n,k;
	cout<<"Enter size of linked list\n";
	cin>>n;
	int data[100];
	cout<<"Enter linked list data in sorted order\n";
	for(int i=0;i<n;i++)
	{
	    cin>>data[i];
	}
	
	struct node* head = NULL;
    
	//constructing linked list
	for (int i = n-1; i >= 0; i--)
		build(&head, data[i]);
	cout<<"Linked list before insertion\nLinked List Data: ";	
    print(head);
    cout<<"\nEnter data you want to insert: ";
    cin>>k;
	sortedInsert(&head, newNode(k));
	cout<<"\nLinked list after insertion\nLinked List Data: ";
	print(head);

	return 0;
}

void build(struct node** head, int data)//function to build linked list
{
	struct node* newNode = (struct node*)malloc(sizeof(struct node));
	newNode->data = data;
	newNode->next = *head;
	*head = newNode;
}
void print(struct node* head)//function to print linked list
{
	struct node* ptr = head;
	while (ptr)
	{
		cout<<ptr->data <<" ";
		ptr = ptr->next;
	}
}

struct node* newNode(int data)
{
	struct node* newNode = (struct node*)malloc(sizeof(struct node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

void sortedInsert(struct node** head, struct node* newNode)//function to insert data in sorted position
{
	//If linked list is empty
	if (*head == NULL || (*head)->data >= newNode->data)
	{
		newNode->next = *head;
		*head = newNode;
		return;
	}

	//Locate the node before insertion
	struct node* current = *head;
	while (current->next != NULL && current->next->data < newNode->data)
		current = current->next;

	newNode->next = current->next;
	current->next = newNode;
}


Output:
Enter size of linked list
4
Enter linked list data in sorted order
12
34
45
56
Linked list before insertion
Linked List Data: 12 34 45 56 
Enter data you want to insert: 25

Linked list after insertion
Linked List Data: 12 25 34 45 56

Learn how you can perform insertion at following places

 

Beginning

nth Position

 

End