"Alternating Skip List"ちぅのが"Exceptional C++ Style"で言及されていたので原文を読んでみる．
http://www.ddj.com/documents/s=882/ddj0008n/
(全文読むにはregistrationが要ります)
普通のリンクだけじゃなくて1個おき，3個おき，7個おき，・・・のリンクを用意することによってSortedAssociativeContainerの要求(簡単に言うとstd::setの機能)を満たせるlistができるとな．ringにすることによって単方向のリンクだけでも逆向きのiterationがO(1)になる．でも，メモリが豊富な環境下ではメモリケチらずに単純に逆方向のリンク張った方が良いかも．ここらへんはpolicyとして切り離したら面白いか．順方向へのiterationがポインタ1つたどるだけで良いというのは集合演算(std::set_union, std::set_intersection, e.t.c.)では結構大きな利点になるかにゃぁ．
＃CUJのarchive読むためにCUJのアカウント作ってたけれど，そのときに「DDJもついでに読めます」とか書いてあって，「DDJって何？どうせ読まないだろうなぁ」と思っていたけれど，まさか役に立つ日が来るとは・・・．
