C++ program to insert in a sorted circular linked list

program to insert in a sorted circular linked list

How to insert in a sorted circular linked list in C++?

C++ program to insert in a sorted circular linked list means to insert the data in a circular linked list in a way that its logical order does not get disturbed. To do this first we need to ensure that the list we are working upon is already sorted else we will have to sort the given list before performing the operation.

Let us learn how to write a program for sorted insert in circular linked using the steps and algorithm discussed in this article.

Steps write a C++ program to insert in a sorted circular linked list

These steps are followed in CPP programming to insert in a sorted circular linked list

  1. Write set of codes to construct circular linked list.
  2. Create a function to build the circular linked list.
  3. Make a function to print the circular linked list data.
  4. Now create a function for insertion in a sorted list.
  5. If current node pointer is equal to head insert new node here.
  6. Else if data of current is greater then data of new node then insert new node before current node.
  7. Else insert new node after current node.
  8. Print the new list with newly inserted node.
Constuct circular linked list

How to build nodes of a in C++?

class Node  

    int data; 
    Node *next; 
}; 
C++ program to insert in a sorted circular linked list

Algorithm to insert in a sorted circular linked list in C++

This algorithm is followed in C++ programming to insert in a sorted circular linked list

  • IF(CURRENT == HEAD)
  • NEW_NODE->NEXT=NEW_NODE
  • HEAD_REF=NEW_NODE
  • CURRENT->DATA>=NEW_NODE->DATA
  • WHILE(CURRENT->NEXT!=HEAD_REF)
  • CURRENT=CURRENT->NEXT
  • CURRENT->NEXT=NEW_NODE
  • NEW_NODE->NEXT=HEAD_REF
  • HEAD_REF=NEW_NODE
  • ELSE
  • WHILE(CURRENT->NEXT!=HEAD_REF&&CURRENT->NEXT->DATA<NEW_NODE->DATA
  • CURRENT=CURRENT->NEXT
  • NEW_NODE->NEXT=CURRENT->NEXT
  • CURRENT->NEXT=NEW_NODE

C++ program for insertion in a sorted circular linked list

#include <iostream>
using namespace std;
//constructing the structure of the node
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 the size of circular linked list\n";
	cin>>n;
	int data[100];
	cout<<"Enter list data in sorted order\n";
	for(int i=0;i<n;i++)
	{
	    cin>>data[i];
	}
	
	struct node* head = NULL;
    
	//creating a  circular linked list
	for (int i = n-1; i >= 0; i--)
		build(&head, data[i]);
	cout<<"Circular linked list before insertion\nCircular linked list data: ";	
    print(head);
    cout<<"\nEnter data you want to insert: ";
    cin>>k;
	sortedInsert(&head, newNode(k));
	cout<<"\nCircular linked list after sorted insertion\nCircular linked list data: ";
	print(head);

	return 0;
}

void build(struct node** head, int data)//method to create circular linked list
{
	struct node* newNode = (struct node*)malloc(sizeof(struct node));
	newNode->data = data;
	newNode->next = *head;
	*head = newNode;
	
}
void print(struct node* head)//method to display the 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));
	struct node* head;
	newNode->data = data;
	newNode->next = head;
	return newNode;
}

void sortedInsert(node** head_ref, node* new_node)  //method for inserting the node at its sorted position
{                                                     
    node* head;
    node* current = *head_ref;  
      
    if (current == head)  
    {  
        new_node->next = new_node;  
        *head_ref = new_node;  
    }  
    
    else if (current->data >= new_node->data)  
    {  
        //If value is smaller than head's value then we need to change next of last node
        while(current->next != *head_ref)  
            current = current->next;  
        current->next = new_node;  
        new_node->next = *head_ref;  
        *head_ref = new_node;  
    }  
      
     
    else
    {  
        
        while (current->next!= *head_ref &&  
            current->next->data < new_node->data)  
        current = current->next;  
      
        new_node->next = current->next;  
        current->next = new_node;  
    }  
}  
Output:
Enter the size of circular linked list
5
Enter list data in sorted order
14
21
28
42
49
Circular linked list before insertion
Circular linked list data: 14 21 28 42 49 
Enter data you want to insert: 35

Circular linked list after sorted insertion
Circular linked list data: 14 21 28 35 42 49

Want to learn more Data Structure?

Learn how to perform insertion at following places in circular linked list