Unrolled linked list
Unrolled linked listは連結リストの変種で、各ノードに格納する要素を複数個にしたものである。CPUキャッシュの利用効率を劇的に向上させるとともに、リストのメタデータ(参照など)によるメモリ消費のオーバーヘッドを削減できる。B木とも関連がある。
典型的なUnrolled linked listの実装は以下のようになる。
各ノードはある一定の最大個数(maxElements個)まで要素を格納できる。maxElementsの大きさは、1つのノードが1から数個程度のキャッシュラインに乗るように設定する。リスト中の要素の位置は、ノードへの参照と配列中の位置のペアで識別される。上記の実装に、リストの一つ前のノードへの参照を追加して、双方向のUnrolled linked listとすることもできる。
新しい要素を挿入する際は、要素が配置されるべきノードを探した上で、elements配列に要素を挿入し、numElementsをインクリメントすればよい。配列がすでに一杯だった場合は、まず現在のノードの前か後ろのいずれかに新しいノードを挿入し、現在のノードの配列の内容の半分を新しいノードへ移動した上で、要素を配列へ追加する。
要素を削除する場合も同様で、削除されるべき要素が入っているノードを探し、elements配列から要素を削除し、numElementsをデクリメントする。numElementsがmaxElements÷2より小さくなった場合は、隣接ノードから現在のノードへ要素を移動させる。隣接ノードの要素もmaxElements÷2より少なかった場合は、要素を移動させてノードをひとつにまとめる。これにより、使用領域の無駄を省くことができる。