#include <stdio.h>
#include <stdlib.h>

int count=0;

struct node
{
    int value;
    struct node *next;
};

struct node *head;

void menu()
{
    printf("\nEnter your desired option\n");
    printf("==========================\n");
    printf("1. Insert first\n");
    printf("2. Insert last\n");
    printf("3. Insert middle\n");
    printf("4. Display\n");
    printf("5. Exit\n");
    printf("6. Count Elements\n");
    printf("7. SOrt Elements \n");
    printf("Enter your choice: ");
}

void insertFirst(int num)
{
    count++;

    struct node *newItem=(struct node *)malloc(sizeof (struct node));
    newItem->value=num;
    newItem->next=NULL;

    if (head==NULL)
        head=newItem;
    else
    {
        newItem->next=head;
        head=newItem;
    }
}


void insertLast(int num)
{
    count++;

    struct node *new_node=(struct node *)malloc(sizeof (struct node));
    new_node->value=num;
    new_node->next=NULL;

    struct node *temp=head;

    if (head==NULL)
        head=new_node;
    else
    {
        while (temp->next!=NULL)
            temp=temp->next;
        temp->next=new_node;
    }
}

void insertMiddle(int num,int loc)
{
    count++;

     struct node *new_node=(struct node *)malloc(sizeof (struct node));

   struct node* temp=new_node;

     temp->value=num;
     temp->next=NULL;

       int count=0;
       struct node* pt=head;

       while(pt->next!=NULL)
       {
           if(count==loc)
           {
               temp->next=pt->next;
               pt->next=temp;
           }
           pt=pt->next;
           count++;
       }


}

void toSort()
{
    int sort=1, temp;
    struct node *new_head, *tail=NULL;

    while(sort)
    {
        new_head=head;
                sort=0;

        while(new_head->next!=tail)
        {
            if (new_head->value>new_head->next->value)
            {
                temp=new_head->value;
                new_head->value=new_head->next->value;
                new_head->next->value=temp;
                sort=1;
            }
            new_head=new_head->next;
        }
        tail=new_head;
    }
}
void toCount(void)
{
    printf("Total Elements %d ",count);

}
void display()
{
    if (head==NULL)
    {
        printf("List Empty\n");
        return;
    }

    struct node *cur=head;

    while (cur!=NULL)
    {

        printf("%i\t", cur->value);
        cur=cur->next;

    }
}

int main( )
{
    int i, n,x,y,z;
    head=NULL;

    while (1)
    {
        menu();
        scanf("%i", &i);

        switch(i)
        {
        case 1:
            scanf("%i", &n);
            insertFirst(n);
            break;
        case 2:
            scanf("%d", &x);
             printf("\n");
            insertLast(x);
            break;
        case 3:
            scanf("%d%d", &y,&z);

            printf("\n");
            insertMiddle(y,z);
            break;
        case 4:
            display();
            break;
        case 5:

            return 0;
         case 6:
             printf("\n");
                toCount();

            break;

        case 7:
             printf("\n");
             toSort();
            break;

        }

    }


    return 0;
}