#include <list>

template<typename T>
class List {
    class Node {
        T x;
        Node* left;
        Node* right;
    };
    class Iterator {
    public:
        Iterator();
        Iterator(Node* node);
        const Iterator operator++ (int);
        const Iterator operator-- (int);
        T& operator* ();
        const Iterator operator== (const Iterator& elem);
        const Iterator operator!= (const Iterator& elem);
        ~Iterator() = default;
        Node* current = nullptr;
    };

private:
    Node* begin_node;
    Node* end_node;

public:
    List();
    void push_back(const T& elem);
    void push_front(const T& elem);
    void pop_back();
    void pop_front();
    size_t size() const;
    Iterator begin();
    Iterator end();
    ~List();
};

template<typename T>
List<T>::Iterator::Iterator() {
    current = nullptr;
}

template<typename T>
List<T>::Iterator::Iterator(Node* node) {
    current = node;
}

template<typename T>
T& List<T>::Iterator::operator*() {
    return *current;
}

template<typename T>
const typename List<T>::Iterator List<T>::Iterator::operator++(int) {
    current = Iterator(current->right);
    return *this;
}

template<typename T>
const typename List<T>::Iterator List<T>::Iterator::operator--(int) {
    current = Iterator(current->left);
    return *this;
}

template<typename T>
typename List<T>::Iterator& List<T>::Iterator::operator==(const Iterator& elem) {
    return elem.current == current;
}

template<typename T>
typename List<T>::Iterator& List<T>::Iterator::operator!=(const Iterator& elem) {
    return !(elem.current == *this);
}

template<typename T>
void List<T>::push_back(const T& elem) {
    Node* new_cur = new Node(elem);
    end_node->right = new_cur;
    new_cur->left = end_node;
    end_node = new_cur;
}

template<typename T>
void List<T>::push_front(const T& elem) {
    Node* new_cur = new Node(elem);
    begin_node->left = new_cur;
    new_cur->right = begin_node;
    begin_node = new_cur;
}

template<typename T>
void List<T>::pop_back() {
    Node* new_cur = end_node->left;
    new_cur->right = nullptr;
    end_node = new_cur;
}

template<typename T>
List<T>::~List() {
    Node* cur = begin_node;
    Node* prev = nullptr;
    while (cur != nullptr) {
        prev = cur;
        cur = cur->right;
        delete prev;
    }
}