#include <algorithm>
#include <memory>

template <typename T>
class linked_list
{
    struct node;

	template <typename Node>
	class node_iterator;

	typedef std::unique_ptr<node> node_ptr;
	
public:
	typedef T value_type;
	typedef std::size_t size_type;
	typedef std::ptrdiff_t difference_type;
	typedef T& reference;
	typedef const T& const_reference;
	typedef node_iterator<node> iterator;
	typedef node_iterator<const node> const_iterator;

private:
	struct node
	{
		node_ptr next;
		value_type value;

		template <typename U>
		node(node_ptr&& next, U&& value)
			: next(std::move(next))
			, value(std::forward<U>(value))
		{}
	};

	template <typename Node>
	class node_iterator
	{
	public:
		typedef T value_type;
		typedef std::ptrdiff_t difference_type;
		typedef T* pointer;
		typedef T& reference;
		typedef std::forward_iterator_tag iterator_category;

	private:
		friend class linked_list;
		typedef node_iterator<const Node> const_iterator_type;
		Node* this_;

	public:
		node_iterator(Node* this_)
			: this_(this_)
		{}

		operator const_iterator_type () const
		{
			return this_;
		}

		bool operator == (const node_iterator& rhs) const
		{
			return this_ == rhs.this_;
		}

		bool operator != (const node_iterator& rhs) const
		{
			return !(*this == rhs);
		}

		const node_iterator& operator ++ ()
		{
			this_ = this_->next.get();
			return *this;
		}

		node_iterator operator ++ (int)
		{
			auto r = *this;
			this_ = this_->next.get();
			return r;
		}

		auto operator * () -> decltype(this_->value)&
		{
			return this_->value;
		}

		auto operator -> () -> decltype(this_->value)*
		{
			return &this_->value;
		}
	};
	
	node_ptr front_;

public:
	template <typename U>
	void push_front(U&& value)
	{
		front_ = node_ptr(new node(std::move(front_), std::forward<U>(value)));
	}

	void pop_front()
	{
		front_ = std::move(front_->next);
	}

	iterator insert_after(const_iterator pos, const value_type& value)
	{
		auto& next = const_cast<node_ptr&>(pos.this_->next);
		next = node_ptr(new node(std::move(next), value));
		return pos.this_->next.get();
	}

	iterator erase_after(const_iterator position)
	{
		const_cast<node_ptr&>(position.this_->next) = std::move(position.this_->next->next);
		return position.this_->next.get();
	}

	iterator begin()
	{
		return front_.get();
	}

	const_iterator begin() const
	{
		return front_.get();
	}

	iterator end()
	{
		return nullptr;
	}

	const_iterator end() const
	{
		return nullptr;
	}
};

#include <iostream>
#include <iterator>
 
int main()
{
	typedef linked_list<char> llist;

  srand(0);
  llist l;
  llist::iterator it = l.begin();
 
  for (int i = 10000000; --i;) {
    if (it != l.end()) {
      if (rand()%2) {
        it = l.insert_after(it, 'a' + (unsigned char)rand() %26);
      } else {
        llist::iterator after = it; ++after;
        if (after == l.end()) goto add_front;
        it = l.erase_after(it);
      }
    } else {
    add_front:
      l.push_front('a' + (unsigned char)rand() %26);
      it = l.begin();
    }
  }
 
  std::ios_base::sync_with_stdio(false);
  std::copy(l.begin(), l.end(), std::ostream_iterator<char>(std::cout, ""));
}