#include <iostream>
#include <memory>

class List {

    class Node;
    typedef std::shared_ptr<Node> Ptr;
    typedef std::weak_ptr<Node> Ref;

    class NodeState {
        friend class List;

        Ptr next_;
        Ref prev_;
        int data_;

        NodeState (int x) : data_(x) {}
        NodeState (const Ptr &p) : next_(p), prev_(p) {}
    };

    class Node {
        friend class List;

        virtual ~Node () = default;
        virtual NodeState & state () = 0;

        Ptr & next () { return state().next_; }
        Ptr prev () { return Ptr(state().prev_); }
        int & data () { return state().data_; }

        void insert (const Ptr &p) {
            p->next() = prev()->next();
            p->state().prev_  = state().prev_;
            prev()->next() = p;
            state().prev_ = p;
        }
    };

    NodeState sentinel_state_;

    Ptr head () { return sentinel_state_.next_; }
    Ptr sentinel () { return head()->prev(); }

    struct NodeImplementation : Node, NodeState {
        NodeImplementation (int x) : NodeState(x) {}
        NodeState & state () { return *this; }
    };

    struct NodeSentinel : Node {
        List &list_;
        NodeSentinel (List &l) : list_(l) {}
        NodeState & state () { return list_.sentinel_state_; }
    };

    class Iterator {
        friend class List;
        Ptr ptr_;
        Iterator (const Ptr &p) : ptr_(p) {}
    public:
        int operator * () const { return ptr_->data(); }
        Iterator operator ++ () { ptr_ = ptr_->next(); return *this; }
        Iterator operator -- () { ptr_ = ptr_->prev(); return *this; }
        bool operator != (const Iterator &i) const { return ptr_ != i.ptr_; }
    };

public:

    typedef Iterator iterator;

    List () : sentinel_state_(std::make_shared<NodeSentinel>(*this)) {}

    iterator begin () { return head(); }
    iterator end () { return head()->prev(); }

    void push_back (int x) {
        sentinel()->insert(std::make_shared<NodeImplementation>(x));
    }
    void push_front (int x) {
        head()->insert(std::make_shared<NodeImplementation>(x));
    }

};

int main ()
{
    auto x = [](List &l) {
        std::cout << "->";
        for (auto x : l) std::cout << '|' << x;
        std::cout << "|\n";
    };

    List l1;
    l1.push_front(3);
    l1.push_front(7);
    l1.push_front(5);
    l1.push_front(1);
    // result: 1, 5, 7, 3
    x(l1);

    List l2;
    l2.push_back(4);
    l2.push_back(8);
    l2.push_back(6);
    l2.push_back(2);
    // result: 4, 8, 6, 2
    x(l2);
}