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