#include <algorithm>
#include <memory>

struct slist_node_base {
  slist_node_base(slist_node_base *next) : next(next) {}
  slist_node_base *next;
};

template <typename T>
class slist {
  struct node : slist_node_base {
    template <typename... Args>
    node(node *n, Args&&... args)
      : slist_node_base(n), data(std::forward<Args>(args)...) {}
    node(node const&)=delete; node& operator=(node const&)=delete;
    node* next() { return static_cast<node*>(slist_node_base::next); }
    void set_next(node* n) { slist_node_base::next = n; }
    T data;
  };
  slist_node_base pointer_to_first;

  node* data() { return static_cast<node*>(&pointer_to_first); }

public:
  slist() : pointer_to_first(data()) {}
 ~slist() {
    for (node *n = data()->next(); n!=data();) {
      std::unique_ptr<node> tmp(n); // Keks für cooky451
      n = n->next();
    }
  }

  slist(slist const& o) =delete;            // Ja, ich bin faul.
  slist& operator=(slist const& o) =delete; // Es fehlen noch die ganzen Range-Funktionen

  class iterator {
    friend class slist;
    slist_node_base *n;
    iterator (node *n) : n(n) {}

    // UB wenn n == end()
    node *as_node() { return static_cast<node*>(n); }

  public:
    typedef std::ptrdiff_t               difference_type;
    typedef std::forward_iterator_tag    iterator_category;
    typedef T                            value_type;
    typedef T*                           pointer;
    typedef T&                           reference;

    iterator& operator++()    { n = n->next; return *this; }
    iterator  operator++(int) { iterator tmp = this; n = n->next; return tmp; }

    bool operator==(const iterator& o) const { return n == o.n; }
    bool operator!=(const iterator& o) const { return n != o.n; }

    T& operator* () { return  as_node()->data; }
    T* operator->() { return &as_node()->data; }
  };

  template <typename... Args>
  iterator emplace_after(iterator i, Args&&... args)
  {
    node *n = new node(i.as_node()->next(), std::forward<Args>(args)...);
    i.as_node()->set_next(n);
    return n;
  }

  iterator erase_after(iterator i)
  {
    std::unique_ptr<node> to_be_deleted(i.as_node()->next()); // Keks für cooky451
    node *ret = to_be_deleted->next();
    i.as_node()->set_next(ret);
    return ret;
  }

  iterator insert_after(iterator i, T const& x) { return emplace_after(i, x); }
  iterator insert_after(iterator i, T&& x)      { return emplace_after(i, std::move(x)); }

  iterator emplace_front(T const& x) { return emplace_after(end(), x); }
  iterator push_front(T const& x) { return emplace_front(x); }
  iterator push_front(T&&      x) { return emplace_front(std::move(x)); }

  void pop_front() { erase_after(data()); }  
  
  iterator begin() { return data()->next(); }
  iterator end()   { return data();         }
};

#include <iostream>
#include <iterator>

int main()
{
  srand(0);
  slist<char> l;
  slist<char>::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 {
        slist<char>::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, ""));
}