Insert element in LL in sorted order
Logic:
1) If LL is empty, then insert the node as head and return it.
2) If value of node to be inserted in LL is less than the value of the head node, then insert the node at start and make it head.
3) Otherwise, traverse through the list and find the appropriate place for the node and check if the value of node to be inserted is less than the value of next node, then insert the node before the next node.
Implementation in C:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* next;
};
struct node* newNode(int newData)
{
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data=newData;
newNode->next=NULL;
return newNode;
}
void print(struct node* n)
{
while(n!=NULL)
{
printf("%d ",n->data);
n=n->next;
}
}
void insert(struct node** ref,struct node* newNode)
{
struct node* current;
if(*ref == NULL || (*ref)->data >= newNode->data)
{
newNode->next=(*ref);
(*ref)=newNode;
}
else
{
current = *ref;
while(current->next!=NULL && current->next->data < newNode->data)
{
current=current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
int main()
{
struct node* head= NULL;
struct node *new_node = newNode(5);
insert(&head,new_node);
new_node=newNode(10);
insert(&head,new_node);
new_node=newNode(3);
insert(&head,new_node);
new_node=newNode(7);
insert(&head,new_node);
new_node=newNode(1);
insert(&head,new_node);
print(head);
getchar();
return 0;
}
Output:
1 3 5 7 10
1) If LL is empty, then insert the node as head and return it.
2) If value of node to be inserted in LL is less than the value of the head node, then insert the node at start and make it head.
3) Otherwise, traverse through the list and find the appropriate place for the node and check if the value of node to be inserted is less than the value of next node, then insert the node before the next node.
Implementation in C:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* next;
};
struct node* newNode(int newData)
{
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data=newData;
newNode->next=NULL;
return newNode;
}
void print(struct node* n)
{
while(n!=NULL)
{
printf("%d ",n->data);
n=n->next;
}
}
void insert(struct node** ref,struct node* newNode)
{
struct node* current;
if(*ref == NULL || (*ref)->data >= newNode->data)
{
newNode->next=(*ref);
(*ref)=newNode;
}
else
{
current = *ref;
while(current->next!=NULL && current->next->data < newNode->data)
{
current=current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
int main()
{
struct node* head= NULL;
struct node *new_node = newNode(5);
insert(&head,new_node);
new_node=newNode(10);
insert(&head,new_node);
new_node=newNode(3);
insert(&head,new_node);
new_node=newNode(7);
insert(&head,new_node);
new_node=newNode(1);
insert(&head,new_node);
print(head);
getchar();
return 0;
}
Output:
1 3 5 7 10
Comments
Post a Comment