#include <stdio.h>
#include <stdlib.h>
struct node
{
    int info;
    struct node *llink,*rlink;
};
typedef struct node *NODE;
NODE insert_front(NODE first,int item);
NODE delete_rear(NODE first);
void display(NODE first);
NODE getnode();
int main()
{   int ch,item;
    NODE first=NULL;
    while(1)
    {
        printf("Enter your choice\n1.Insert\n2.Delete\n3.Display\n4.Exit");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:printf("Enter the element to be inserted");
                    scanf("%d",&item);
                    first=insert_front(first,item);
                    break;
            case 2:first=delete_rear(first);
                    break;
            case 3:display(first);
                    break;
            case 4:exit(0);
        }
    }
    return 0;
}
NODE getnode()
{
    NODE x;
    x=(NODE)malloc(sizeof(struct node));
    return x;
}
NODE insert_front(NODE first,int item)
{
    NODE temp;
    temp=getnode();
    temp->info=item;
    if(first==NULL)
    {
        temp->llink=temp;
        temp->rlink=temp;
        return temp;
    }
    if(first->rlink==first&&first->llink==first)
    {
        temp->rlink=first;
        temp->llink=first;
        first->rlink=temp;
        first->llink=temp;
        return temp;
    }

    NODE t;
    t=first->llink;
    first->llink=temp;
    temp->rlink=first;
    temp->llink=t;
    t->rlink=temp;
    return temp;
}
NODE delete_rear(NODE first)
{
    if(first==NULL)
    {
        printf("List is empty\n");
        return first;
    }
    if(first->rlink==first&&first->llink==first)
    {
        free(first);
        return NULL;
    }
    NODE t;
    t=first;
    while(t->rlink!=first)
    {
        t=t->rlink;
    }
    NODE p;
    p=t->llink;
    printf("Deleted data is %d",t->info);
    p->rlink=first;
    t->llink=NULL;
    t->rlink=NULL;
    first->llink=p;
    free(t);
    return first;
}
void display(NODE first)
{
    if(first==NULL)
    {
        printf("List is empty\n");
        return;
    }
    NODE t;
    t=first;
    while(t->rlink!=first)
    {
        printf("%d\t",t->info);
        t=t->rlink;
    }
    printf("%d",t->info);
    return;
}