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