#include <iostream>
using namespace std;
#define null NULL
class node
{
    public :
    int data;
    node * next;
    node * prev;
};
class doublelinkedlist
{
    public :
    node * head;
    doublelinkedlist()
    {
        head=null;
    }
    void insert_first(int x)
    {
        node * newnode=new node;
        newnode->data=x;
        newnode->next=head;
        newnode->prev=null;
        if(head!=null)
        {
            head->prev=newnode;
        }
        head=newnode;
    }
    void insert_last(int x)
    {
        node * newnode=new node;
        newnode->data=x;
        newnode->next=null;
        newnode->prev=null;
        if(head==null)
        {
            head=newnode;

        }
        else
        {
            node * temp=head;
            while(temp->next!=null)
            {
                temp=temp->next;
            }
            temp->next=newnode;
            newnode->prev=temp;
        }
    }
    void delete_first()
    {
        if(head==null)
        {
            cout<<"invalid operation \n";
            return ;
        }
        else
        {
            node * temp=head;
            head=head->next;
            if(head!=null)
            {

            head->prev=null;
            }
            delete temp;
        }
    }
    void delete_last()
    {
        if(head==null)
        {
            cout<<"list empty\n";
            return ;
        }
        node * temp=head;
        while(temp->next!=null)
        {
            temp=temp->next;
        }
        if(temp->prev==null)
        {
            head=null;
        }
        else
        {
            temp->prev->next=null;
        }
        delete temp;
    }
    void delete_byvalue(int x)
    {
        node * temp = head;
        while(temp!=null&& temp->data!=x)
        {
           temp=temp->next;
        }
            if(temp==null)
            {
                cout<<"not found the value \n";
                return ;
            }
            if(temp->prev==null)
            {
                head=temp->next;
            }
            else
            {
            temp->prev->next=temp->next;
            }
            if(temp->next!=null)
            {
                temp->next->prev=temp->prev;
            }
            delete temp;
    }
    void printfrombegging()
    {
        node * temp=head;
        if(head==null)
        {
            cout<<"list is empty\n";
            return ;
        }
        while(temp!=null)
        {
            cout<<temp->data <<" ";
            temp=temp->next;
        }
        cout<<"\n";

    }
    void printfromend()
    {
        if(head==null)
        {
            cout<<"list is empty\n";
            return ;
        }
        node * temp=head;
        while(temp->next!=null)
        {
            temp=temp->next;
        }
        if(temp->prev==null)
        {
            cout<<temp->data<<"\n";
            return ;
        }
        while(temp!=null)
        {
            cout<<temp->data<<" ";
            temp=temp->prev;
        }

    }
};
int main()
{
    doublelinkedlist test;
    test.insert_last(10);
    test.insert_last(20);
    test.insert_last(30);

    cout<<"Original List: ";
    test.printfrombegging();

    test.insert_first(5);

    cout<<"After Insert First: ";
    test.printfrombegging();

    cout<<"Backward: ";
    test.printfromend();

    test.delete_first();

    cout<<"\nAfter Delete First: ";
    test.printfrombegging();

    test.delete_last();

    cout<<"After Delete Last: ";
    test.printfrombegging();

    test.delete_byvalue(20);

    cout<<"After Delete Value 20: ";
    test.printfrombegging();

    test.delete_byvalue(100);

    cout<<"Final List: ";
    test.printfrombegging();

    return 0;
}