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

Comments

Popular posts from this blog

Three mislabeled Jar

Difference between Macro And function