Unrolled linked list
Unrolled linked listではリスト中の要素数に対するvのオーバーヘッドを効果的に削減しており、maxElementsが大きい場合や、要素一つのサイズが小さい場合などにオーバーヘッドの削減効果がより大きくなる。
要素一つのサイズが特に小さい場合(例えば1ビットなど)、データに対するオーバーヘッドのサイズは(データモデルにもよるが)最大64倍にもなる。その上、多くのメモリアロケータではメモリも割り当ての度に少量のメタデータを作成するため、オーバーヘッドvがその分増加する。これらの理由により、Unrolled linked listはより魅力的となる。
また、Unrolled linked listを使用することでCPUキャッシュの利用効率を向上させることもできる。各ノードが一杯の状態で、キャッシュラインのサイズをbとすると、リスト全体の走査はおよそ n / B {\displaystyle n/B} 回のキャッシュミスで行える。さらに、各要素一つあたりのサイズがキャッシュラインのサイズと比較して小さければ、通常の連結リストと比較して少ない回数のキャッシュミスでリスト中を走査することができる。いずれの場合でも、操作に必要な時間はリストのサイズに比例して増加する。