#include <iostream>
using namespace std;

struct Node {
        int value;
        Node *next, *prev;
    };
struct LinkedList{
        Node *head;
        Node *tail;

    LinkedList(){
        head = NULL;
        tail = NULL;
    }

    void insertBegining(int value){
        Node *node = new Node();
        node->value = value;
        node->next = head;
        node->prev = NULL;
        head = node;
    }
    void insertEnd(int value){
        Node *node = new Node();
        node->value = value;
        node->next = NULL;
        node->prev = tail;
        tail = node;
    }
    int removeBegining(){
        Node *node = head;
        int ret = node->value;
        head = head->next;
        head->prev = NULL;
        delete node;
        return ret;
    }
    int removeEnd(){
        Node *node = tail;
        int ret = node->value;
        tail = tail->prev;
        tail->next = NULL;
        delete node;
        return ret;
    }
    int insertAfter(Node *node, Node *newNode)
    {
        newNode->next = node->next;
        node->next = newNode;
        newNode->prev = node;
        newNode->next->prev = newNode;
    }
    int insertBefore(Node *node, Node *newNode)
    {
        newNode->prev = node->prev;
        node->prev = newNode;
        newNode->next = node;
        newNode->prev->next = newNode;
    }
};
int main() {
    LinkedList list;
    Node *node, *node2;
    node->value = 2;
    node2->value = 3;
    list.insertBegining(4);
    list.insertBegining(1);
    list.insertAfter(list.head, node);
    list.insertBefore(list.tail, node2);
    list.insertEnd(5);

    cout << list.removeEnd() << endl;
    cout << list.removeEnd() << endl;
    cout << list.removeEnd() << endl;
    cout << list.removeEnd() << endl;
    cout << list.removeEnd() << endl;

    return 0;
}