#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
Login/Signup to comment