CPP Program to implement insertion sort

Source Code : 

#include<iostream>

using namespace std;

struct list

{

int data;

list *next;

};

list* InsertnList(list *head, int n)

{

list *newnode = new list;

list *temp = new list;

newnode->data = n;

newnode->next = NULL;

if(head == NULL)

{

head = newnode;

return head;

}

else

{

temp = head;

if(newnode->data < head->data)

{

newnode->next = head;

head = newnode;

return head;

}

while(temp->next != NULL)

{

if(newnode->data < (temp->next)->data)

break;

temp=temp->next;

}

newnode->next = temp->next;

temp->next = newnode;

return head;

}

}

int main()

{

   int n, i, num;

   list *head = new list;

   head = NULL;

   

   cout<<"Enter the number of data element to be sorted: ";

   cin>>n;

   

   for(i=0;i<n;i++)

   {

    cout<<"Enter element "<<i+1<<": ";

    cin>>num;

    head = InsertnList(head, num);

   }

   

   cout<<"Sorted Data ";

   while(head != NULL)

   {

    cout<<"->"<<head->data;

    head = head->next;

   }

   

   return 0;

}

Program Output :