#include<stdio.h>
#include<stdlib.h>
#define MALLOC(p,n,type)\
p=(type*)malloc(n*sizeof(type));\
if(p==NULL)\
{\
printf("Insufficient memory\n");\
exit(0);\
}
struct node
{ 
    int info;
    struct node *llink;
    struct node *rlink;
};
typedef struct node* NODE;
NODE insertion_front(int, NODE);
void display(NODE);
NODE deletion_front(NODE);
NODE insertion_rear(int, NODE);
NODE deletion_rear(NODE);
int count_nodes(NODE);
void search(NODE, int);
void main()
{
    NODE first; 
    int item, choice, pos;
    first = NULL;         
    for (;;) {
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:
                    scanf("%d", &item);
                    first = insertion_front(item, first);
                    break;
            case 2:
                    first = deletion_front(first);       
                    break;
            case 3:
                    display(first);
                    break;
            case 4:
                    scanf("%d", &item);
                    first = insertion_rear(item, first); 
                break;
            case 5:
                    first = deletion_rear(first);
                    break;
            case 6:
                    printf("No of nodes in DLL = %d\n", count_nodes(first));
                    break;
            case 7:
                   scanf("%d", &item);
                   search(first, item);
                   break;
            case 8:exit(0);
        }
    }
}
NODE insertion_front(int item, NODE first)
{
    NODE temp;
    MALLOC(temp, 1, struct node);
    temp->info = item;
    temp->llink=NULL;
    temp->rlink=NULL;
    if(first==NULL)
    {
        return temp;
    }
    temp->rlink = first;
    first->llink=temp;
    return temp;
}
void display(NODE first)
{
    NODE temp;
    if (first == NULL)
    {               
        printf("Empty DLL - Cannot display\n");
        return;
    }
    temp = first;                     
    while (temp != NULL)
    {
          printf("%d", temp->info);
            temp = temp->rlink;
            printf("->");
    }
    printf("\n");
}
NODE deletion_front(NODE first)
{
    NODE temp;
    if (first == NULL)
    {               
        printf("Empty DLL - Cannot delete\n");
        return NULL;
    }
     if(first->rlink==NULL)
    {
      printf("Deleted element from DLL is %d\n", first->info);
      free(first);
      return NULL;
    }             
     temp = first;
    first = first->rlink;
    first->llink=NULL;
    printf("Deleted element from DLL is %d\n", temp->info);
    free(temp);
    return first;
}
NODE insertion_rear(int item, NODE first)
{
    NODE temp, cur;
    MALLOC(temp, 1, struct node);
    temp->info = item;
    temp->llink = NULL;
    temp->rlink=NULL;
    if (first == NULL)
    {               
        return temp;
    }
    cur = first;                       
    while (cur->rlink != NULL)
    {
        cur = cur->rlink;
    }
    cur->rlink = temp;
    temp->llink=cur;
    return first;
}
NODE deletion_rear(NODE first)
{
    NODE prev, cur;
    if (first == NULL)
    {               
        printf("Empty DLL - Cannot delete\n");
        return NULL;
    }
    if (first->rlink == NULL)
    {         
        printf("Deleted element from DLL is %d\n", first->info);
        free(first);
        return NULL;
    }
    prev = NULL;                      
    cur = first;
    while (cur->rlink != NULL)
    {
        prev = cur;
        cur = cur->rlink;
    }
    printf("Deleted element from DLL is %d\n", cur->info);
    free(cur);
    prev->rlink = NULL;
    return first;
}
int count_nodes(NODE first)
{
    int count = 0;
    NODE temp = first;
    while (temp != NULL)
    {
        count++;
        temp = temp->rlink;
    }
    return count;
}
void search(NODE first, int item)
{
    NODE temp = first;
    int found = 0;
    while (temp != NULL)
    {
        if (temp->info == item)
        {
            found = 1;
            break;
        }
        temp = temp->rlink;
    }
    if (found)
    {
        printf("%d is found in DLL\n", item);
    } else {
        printf("%d is not found in DLL\n", item);
    }
}