#include <cstddef>
#include <iostream>

using namespace std;

template<typename T>
class Node {
public:
    Node() = default;

    Node(const T &data, Node *prev, Node *next)
            : data_(data), prev_(prev), next_(next) {}

    T data_;
    Node *prev_ = nullptr;
    Node *next_ = nullptr;
};

template<typename T>
class ListIterator {
public:
    using Iterator = Node<T> *;

    ListIterator(Node<T> *elem, Node<T> *tail)
            : iter_(elem), tail_(tail) {}

    ListIterator<T> &operator++() {
        iter_ = iter_->next_;
        return *this;
    }

    ListIterator<T> &operator--() {
        if (iter_ == nullptr)
            iter_ = tail_;
        else
            iter_ = iter_->prev_;
        return *this;
    }

    T &operator*() {
        return iter_->data_;
    }

    const T &operator*() const {
        return iter_->data_;
    }

    bool operator==(const ListIterator &other) {
        return iter_ == other.iter_;
    }

    bool operator!=(const ListIterator &other) {
        return iter_ != other.iter_;
    }

private:
    Iterator iter_;
    Iterator tail_;
};

template<typename T>
class List {
public:
    List() : head_(nullptr),
             tail_(nullptr),
             size_(0) {}

    List(const List &other) {
        auto tmp = other.head_;
        for (; tmp != nullptr; tmp = tmp->next_) {
            this->push_back(tmp->data_);
        }

        size_ = other.size_;
    }

    List &operator=(const List &other) {
        Node<T> *cur = nullptr;
        while (head_) {
            cur = head_;
            head_ = head_->next_;
            delete cur;
        }

        auto tmp = other.head_;
        for (; tmp != nullptr; tmp = tmp->next_) {
            this->push_back(tmp->data_);
        }

        size_ = other.size_;
        return *this;
    }

    void push_back(const T &elem) {
        auto adding = new Node<T>(elem, tail_, nullptr);
        tail_ = adding;
        if (adding->prev_) {
            adding->prev_->next_ = adding;
        } else {
            head_ = adding;
        }
        ++size_;
    }

    void push_front(const T &elem) {
        auto adding = new Node<T>(elem, nullptr, head_);

        adding->prev_ = head_->prev_;
        head_->prev_ = adding;

        if (adding->prev_) {
            adding->prev_->next_ = adding;
        } else {
            head_ = adding;
        }
        ++size_;
    }

    void del(Node<T> *nd) {
        if (nd != nullptr) {
            if (nd->prev_)
                nd->prev_->next_ = nd->next_;

            if (nd->next_)
                nd->next_->prev_ = nd->prev_;

            if (nd == head_)
                head_ = nd->next_;

            if (nd == tail_)
                tail_ = nd->prev_;

            delete nd;

            size_--;
        }
    }

    void pop_back() {
        del(tail_);
    }

    void pop_front() {
        del(head_);
    }

    size_t size() const {
        return size_;
    }

    bool empty() const {
        return !size_;
    }

    ListIterator<T> begin() {
        return ListIterator<T>(head_, tail_);
    }

    ListIterator<T> end() {
        return ListIterator<T>(tail_->next_, tail_);
    }

    ~List() {
        Node<T> *cur(head_);
        while (cur) {
            auto nxt(cur->next_);
            delete cur;
            cur = nxt;
        }
    }

private:
    Node<T> *head_ = nullptr;
    Node<T> *tail_ = nullptr;
    size_t size_;
};