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

The procedure describes a C ++ program to insert into an ordered circular linked list:

These steps are performed in CPP programming and inserted into an ordered circular linked list.

  1. Write a set of code to create a circular linked list.
  2. Create a function that creates a circular linked list.
  3. Create a function that generates circular linked list data.
  4. Next, create a function to insert into the ordered list.
  5. If the current node pointer equals the head, insert a new node here.
  6. Otherwise, if the current data is larger than the data for the new node, insert the new node before the current one.
  7. Otherwise, insert a new node after the current node.
  8. Print a new list containing the newly inserted nodes.

Sorted

Algorithm for inserting into an ordered circular linked list in C ++:

This algorithm is used in C ++ programming and is inserted into an ordered 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

For example:

Sorted

Sorted

Sorted

Sorted

Here Code:

#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)
{
    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;
          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)
{
          struct node* newNode = (struct node*)malloc(sizeof(struct node));
          newNode->data = data;
          newNode->next = *head;
          *head = newNode;
}
void print(struct node* head)
{
          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) 
{                                                    
    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) 
    { 
        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; 
    } 
}

Complexity Analysis:

  • Time Complexity: O (n) where n is the number of nodes in the specified linked list.

Recommended Articles:

  1. Traversal in Circular Linked List
  2. How to split a circular linked list into two halves?
  3. How to reverse a string using stack?
  4. Insertion in Circular Singly Linked List
  5. How to write C functions that modify head pointer of a Linked List?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 97 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
4 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] C++ program to insert in a sorted circular linked list? […]

trackback

[…] C++ program to insert in a sorted circular linked list? […]

trackback

[…] C++ program to insert in a sorted circular linked list? […]

trackback

[…] C++ program to insert in a sorted circular linked list? […]

You cannot copy content of this page
Scroll Up
4
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.