#include <stdio.h>
#include <stdlib.h>
struct node 
{
    int info;
    struct node *link;
};
typedef struct node* NODE;
NODE insert_front(int ,NODE );
NODE delete_front(NODE );
NODE insert_rear(int ,NODE );
NODE delete_rear(NODE );
void display(NODE );
void search(NODE ,int );
int node_count(NODE );
int main()
{
    int ch,item;
    NODE first;
    first=NULL;
    while(1)
    {
        scanf("%d",&ch);
        switch (ch)
        {
            case 1:
                scanf("%d",&item);
                first=insert_front(item,first);
                break;
            case 2:
                first=delete_front(first);
                break;
            case 3:
                display(first);
                break;
            case 4:
                scanf("%d", &item);
                first=insert_rear(item,first);
                break;
            case 5:
                first=delete_rear(first);
                break;
            case 6:
                printf("\nNo of nodes in SLL = %d",node_count(first));
                break;
            case 7:
                scanf("%d",&item);
                search(first,item);
                break;
            case 8:exit(0);
            default:
                printf("Invalid Choice");
        }
    }
}
NODE insert_front(int item,NODE first)
{
    struct node* temp;
    temp=(struct node*)malloc(1*sizeof(struct node));
    temp->info=item;
    temp->link=first;
    return temp;
}
NODE delete_front(NODE first)
{
    NODE temp;
    if(first==NULL)
    {
        printf("THE LIST IS EMPTY");
        return NULL;
    }
    else
    {
        temp=first;
        first=first->link;
        printf("\nDeleted element from SLL is %d",temp->info);
        free(temp);
        return first;
    }
}
NODE insert_rear(int item,NODE first)
{
    NODE temp,cur;
    temp=(struct node*)malloc(1*sizeof(struct node));
    temp->info=item;
    temp->link=NULL;
    if(first==NULL)
    {
        return temp;
    }
    cur=first;
    while(cur->link!=NULL)
    {
        cur=cur->link;
    }
    cur->link=temp;
    return first;
}
NODE delete_rear(NODE first)
{
    NODE prev,cur;
    if(first==NULL)
    {
        printf("empty sll");
        return NULL;
    }
    if(first->link==NULL)
    {
        printf("\nDeleted element from SLL is %d",first->info);
        free(first);
        return NULL;
    }
    prev=NULL;
    cur=first;
    while(cur->link!=NULL)
    {
        prev=cur;
        cur=cur->link;
    }
    printf("\nDeleted element from SLL is %d",cur->info);
    free(cur);
    prev->link=NULL;
    return first;
}
void display(NODE first)
{
    NODE temp;
    if(first==NULL)
    {
        printf("\nEmpty SLL - Cannot display");
        return;
    }
    temp=first;
    while(temp!=NULL)
    {
        printf("\n%d",temp->info);
        temp=temp->link;
        printf("->");
    }
}
void search(NODE first,int item)
{
   NODE temp=first;
   int flag=0;
   while(temp!=NULL)
   {
       if(temp->info==item)
       {
           flag=1;
           break;
       }
       temp=temp->link;
   }
   if(flag)
   {
       printf("\n%d is found in SLL",item);
   }
   else
   {
       printf("\n%d is not found in SLL",item);
   }
}
int node_count(NODE first)
{
    int count=0;
    NODE temp=first;
    while(temp!=NULL)
    {
        count++;
        temp=temp->link;
    }
    return count;
}