C++ 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.

program to insert in a sorted circular linked list

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

Run
#include<iostream> //haeder files
using namespace std;

// create node
struct Node { 
    int data; 
    struct Node *next; 
}; 

// this function for insert the new node in linked list 
void sortedInsert(struct Node** head_ref, struct Node* new_node){ 
    struct Node* present = *head_ref; 
    
    // Case 1 when list is empty
    if (present == NULL){ 
        new_node->next = new_node; 
        *head_ref = new_node; 
    } 

    // Case 2 when the node insert before the head
    else if (present->data >= new_node->data){ 
        //when value is smaller than head's value

        while( present->next != *head_ref) 
            present = present->next; 
        
        present->next = new_node; 
        new_node->next = *head_ref; 
        *head_ref = new_node; 
    } 

    // Case 3 when node insert in after head in somewhere
    else{ 
        //Locate the node before the point of insertion 
        
        while ( present->next!= *head_ref && present->next->data < new_node->data) 
            present = present->next; 
 
        new_node->next =present->next; 
        present->next = new_node; 
    } 
} 

//this Function to print nodes in a given linked list
void printList(struct Node *start) { 
    
    struct Node *temp; 

    if(start != NULL){ 
        temp = start; 
        cout<<"\n"; 
        do { 
            cout<<temp->data<<" "; 
            temp = temp->next; 
        } while(temp != start); 
    } 
} 

// main method start
int main(){
    
    int arr[] = {12, 56, 2, 11, 1, 90}; 
    int list_size, i; 

    // start with empty linked list 
    struct Node *start = NULL; 
    struct Node *temp; 

    // Create linked list from the array arr[]. 
    // Created linked list will be 1->2->11->12->56->90 
    for (i = 0; i< 6; i++) { 
        temp = (struct Node *)malloc(sizeof(struct Node)); 
        temp->data = arr[i]; 
        sortedInsert(&start, temp); 
    } 

    printList(start); 

    return 0; 
} 
Output:
1 2 11 12 56 90

Want to learn more Data Structure?

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