論文は"A Pragmatic Implementation of Non-Blocking Linked-Lists"
アルゴリズムを簡単に図示する(原論文の図に注釈したもの):
図の上部は避けなければならない状況の説明で、削除(10)と挿入(20)が並行して
実行された場合で、挿入するノード(20)が孤児になることをしめしている。
図の下部は今回実装したアルゴリズムで、削除するノードにマーキングして上記
の状況を避ける。
これは前回のLazy Listをごく自然にLock-Free化したもの。両者の比較や、この
アルゴリズムの改良版は次回以降で。