struct list_node
{
    list_node* prev;
    list_node* next;

    list_node()
        : prev(this)
        , next(this)
    { }

    void link(list_node* node)
    {
        list_node* temp_prev = node->prev;
        list_node* temp_next = next;

        node->prev = temp_next->prev;
        temp_next->prev = temp_prev;

        next = temp_prev->next;
        temp_prev->next = temp_next;
    }

    void push_front(list_node* node)
    {
        link(node);
    }

    void push_back(list_node* node)
    {
        prev->link(node);
    }

    void merge(list_node* head)
    {
        list_node* first_value = head->next;

        if (first_value != head)
        {
            head->unlink();

            push_back(first_value);
        }
    }

    void unlink()
    {
        link(this);
    }

    bool empty() const
    {
        return next == this;
    }

    struct iterator
    {
    protected:
        list_node* value;

    public:
        iterator(list_node* value)
            : value(value)
        { }

        list_node& operator*() const
        {
            return *value;
        }

        bool operator!=(const iterator& rhs) const
        {
            return rhs.value != value;
        }

        iterator& operator++()
        {
            value = value->next;

            return *this;
        }

        iterator& operator--()
        {
            value = value->prev;

            return *this;
        }
    };

    iterator begin()
    {
        return iterator(next);
    }

    iterator end()
    {
        return iterator(this);
    }
};