graph (2)

リストからツリーという空間方向への拡大も複雑さを増大させますが，時間変化するグラフというのも厄介な代物です．しかも問題は一通りではないかもしれません．
例えば同一のリストに複数のスレッドから操作される場合は特別な注意が必要でしょう．Microsoft はカーネル内部のリソース管理に "Interlocked Singly Linked Lists" と呼ばれるリンクリストを利用しています．このリンクリストは操作時に lock が必要ないという性質を持っています．Windows XP 以降では API として公開され，一般開発者も利用できるようになりました．
Interlocked Singly Linked Lists
また，マルチスレッド環境下でのヒープマネージャがボトルネックになることが多いと言われている理由のひとつが，メモリブロックを管理するリスト操作をスレッド間で調停しなければならないというものです．パフォーマンスの観点からも考えるべきことは多いです．