#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<process.h>

struct node
{
    int info;
    struct node *link;
}*start;

void Create_List(int data)
{
    struct node *q,*tmp;

    tmp= (struct node*)malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=NULL;
    if(start==NULL)
        start=tmp;
    else
    {
        q=start;
        while(q->link!=NULL)
            q=q->link;
        q->link=tmp;
    }
}

void AddatBegin(int data)
{
    struct node *tmp;
    tmp=(struct node*)malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=start;
    start=tmp;
}

void insertLast(int data)
{
    struct node *q=start,*tmp;
    while(q!=NULL && q->link!=NULL)
    {
        q=q->link;
    }
    tmp=(struct node*)malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=NULL;
    if(q!=NULL)
    {
        q->link=tmp;
    }
    else
    {
        start=tmp;
    }
}

void insertBefore(int data,int pos)
{
    struct node *q;
    q=(struct node*)malloc(sizeof(struct node));
    q->info=data;
    int i;
    struct node *tmp=start;
    if(pos==1)
    {
        AddatBegin(data);
        return;
    }
    for(i=2;i<pos;i++)
    {
        tmp=tmp->link;
    }
    q->link=tmp->link;
    tmp->link=q;

}

int getFirst()
{
    struct node *q=start;
    if(q!=NULL)
    {
        return q->info;
    }
    else
    {
        printf("\nNot Found!!!\n");
    }
}

int getLast()
{
    struct node *q=start;
    if(q==NULL)
    {
        printf("\nList is empty!!!\n");
    }
    else
    {
        while(q->link!=NULL)
        {
            q=q->link;
        }
        return q->info;
    }
}

int get(int pos)
{
    struct node *q=start;
    int c=1;
    while(q!=NULL)
    {
        if(c==pos)
        {
            printf("\nData: %d\n", q->info);
        }
        q=q->link;
        c++;
    }
    printf("\nThere's no element in that position!!!\n");
}

void DelfirstNode()
{
    struct node *tmp,*q;
        tmp=start;
        start=start->link;
        free(tmp);
        return;

}

void delLast()
{
    struct node *q=start,*tmp;
    if(start->info!=NULL)
    {
        while(q->link->link!=NULL)
        {
            q=q->link;
        }
        tmp=q->link;
        free(tmp);
        q->link=NULL;
    }

}

void delAt(int pos)
{
    struct node *q,*tmp;
    q=start;
    int c=0;
    if(start->info!=NULL)
    {
        if(pos==1)
        {
            DelfirstNode();
            return;
        }
        while(q->link!=NULL)
        {
            if(c==pos-2)
            {
                tmp=q->link;
                q->link=tmp->link;
                free(tmp);
                return;
            }
            q=q->link;
            c++;
        }
    }
}
void Display()
{
    struct node *q;
    if(start == NULL)
    {
        printf ("\n\nList is empty");
        return;
    }
    q=start;
    printf("\n\nList is : ");
    while(q!=NULL)
    {
        printf ("%d ", q->info);
        q=q->link;
    }
    printf ("\n");
    getch();
}

int search_list(int data)
{
    struct node *q=start;
    int pos=1;
    while(q!=NULL)
    {
        if(q->info==data)
        {
            printf("\nFound at position = %d\n", pos);
            getch();
        }
        q=q->link;
        pos++;
    }
    if(q==NULL)
    {
        printf("\nNot found!");
        getch();
    }
}

void Rev()
{
    struct node *p1,*p2,*p3;
    if(start->link==NULL)
        return;
    p1=start;
    p2=p1->link;
    p3=p2->link;
    p1->link=NULL;
    p2->link=p1;
    while(p3!=NULL)
    {
        p1=p2;
        p2=p3;
        p3=p3->link;
        p2->link=p1;
    }
    start=p2;
}

void main()
{
    int choice,n,m,position,i;
    start=NULL;
    while(1)
    {
        printf("============================================\n");
        printf("SINGLY LINKED LIST PROGRAM\n");
        printf("============================================\n");
        printf ("1.Create List\n");
        printf ("2.Insert an element at the beginning\n");
        printf ("3.Insert an element to the end of the list\n");
        printf ("4.Insert an element at a specific position\n");
        printf ("5.Display the complete list\n");
        printf ("6.Display first element\n");
        printf ("7.Display last element\n");
        printf ("8.Display from a specific position\n");
        printf ("9.Delete First Node\n");
        printf ("10.Delete last node\n");
        printf ("11.Delete node from specific position\n");
        printf ("12.Search\n");
        printf ("13.Reverse\n");
        printf ("14.Quit\n");
        printf ("\nEnter your choice:");
        scanf ("%d",&choice);
        switch (choice)
        {
        case 1:
            printf ("\n\nHow many nodes you want:");
            scanf ("%d",&n);
            for(i = 0; i<n; i++)
            {
                printf ("\nEnter element %d: ", i+1);
                scanf ("%d",&m);
                Create_List(m);
            }
            printf("\n");
            break;

        case 2:
            printf("\nEnter data: ");
            scanf("%d", &n);
            AddatBegin(n);
            printf("\nData inserted successfully!!!\n");
            break;

        case 3:
            printf("\nEnter the data to insert: ");
            scanf("%d", &n);
            insertLast(n);
            printf("\nData inserted successfully!!!\n");
            break;

        case 4:
            printf("\nEnter data: ");
            scanf("%d", &m);
            printf("\nEnter position: ");
            scanf("%d", &n);
            insertBefore(m,n);
            printf("\nData inserted successfully!!!\n");
            break;

        case 5:
            Display();
            break;

        case 6:
            printf("\nFirst element of the list: %d\n", getFirst());
            break;

        case 7:
            {
                printf("\nLast element of the list: %d", getLast());
                break;
            }

        case 8:
            printf("\nEnter the position: ");
            scanf("%d", &m);
            get(m);
            break;

        case 9:
            DelfirstNode();
            printf("\nNode deleted successfully!!!\n");
            break;

        case 10:
            delLast();
            printf("\nNode deleted successfully!!!\n");
            break;

        case 11:
            printf("\nEnter position: ");
            scanf("%d", &n);
            delAt(n);
            printf("\nNode deleted successfully!!!\n");
            break;

        case 12:
            printf("\nEnter the element to search: ");
            scanf("%d", &n);
            search_list(n);
            break;

        case 13:
            Rev();
            printf("\nList reversed successfully!!!\n");
            break;

        case 14:
            exit(0);
        default:
            printf ("\n\nWrong choice");
        }
    }
}