#include <iostream>
using namespace std;

struct node {
    int info;
    node *next;
    node *prev;
};

struct DoublyLinkedList {
    node * head;

    void init() {
        head = NULL;
    }

    void insertFront(int x) {
        node * new_node = new node;
        new_node->info = x;
        new_node->next = NULL;
        new_node->prev = NULL;

        if(head == NULL) {
            head = new_node;
        }
        else {
            new_node->next = head;
            head->prev = new_node;
            head = new_node;
        }
    }

    void insertBack(int x) {
        node * new_node = new node;
        new_node->info = x;
        new_node->next = NULL;
        new_node->prev = NULL;

        if(head == NULL) {
            head = new_node;
        }
        else {
            node * tmp = head;
            while(tmp->next != NULL) {
                tmp = tmp->next;
            }

            tmp->next = new_node;
            new_node->prev = tmp;
        }
    }

    void deleteFront() {
        if(head != NULL) {
            if(head->next == NULL) {
                delete head;
                head = NULL;
            }
            else {
                head = head->next;
                delete head->prev;
                head->prev = NULL;
            }
        }
    }

    void deleteBack() {
        if(head != NULL) {
            if(head->next == NULL) {
                delete head;
                head = NULL;
            }
            else {
                node * tmp = head;
                while(tmp->next != NULL) {
                    tmp = tmp->next;
                }
                tmp->prev->next = NULL;
                delete tmp;
                tmp = NULL;
            }
        }
    }

    void deleteNode(int x) {
        if(head != NULL) {
            if(head->info == x) {
                deleteFront();
            }
            else {
                node *tmp = head;
                while(tmp != NULL and tmp->info != x) {
                    tmp = tmp->next;
                }

                if(tmp != NULL) {
                    tmp->prev->next = tmp->next;
                    tmp->next->prev = tmp->prev;

                    delete tmp;
                    tmp = NULL;
                }
            }
        }
    }

    void deleteNode(node * x) {
        if(head != NULL) {
            if(head == x) {
                deleteFront();
            }
            else {
                node *tmp = head;
                while(tmp != NULL and tmp != x) {
                    tmp = tmp->next;
                }

                if(tmp != NULL) {
                    tmp->prev->next = tmp->next;
                    tmp->next->prev = tmp->prev;

                    delete tmp;
                    tmp = NULL;
                }
            }
        }
    }
    void print() {
        node * tmp = head;
        node * back = NULL;
        while(tmp != NULL) {
            cout << tmp->info << " --> ";
            back = tmp;
            tmp = tmp->next;
        }

        cout << endl;

        while(back != NULL) {
            cout << back->info << " <-- ";
            back = back->prev;
        }
        cout << endl;
    }

};

int main() {

    DoublyLinkedList dll;
    dll.init();

    dll.insertFront(1);
    dll.insertFront(2);
    dll.insertFront(3);

    dll.insertBack(4);
    dll.insertBack(5);

    dll.print();

    dll.deleteNode(1);

    dll.print();

    return 0;
}

// 108 105 110 107 101 100 108 111 111 112