Unrolled linked list
Unrolled linked listの最大の利点は、使用領域を削減できることにある。たかだか1つのノードを除けば、それ以外の全てのノードは常に最低でも半分以上埋まっている状態になる。要素の挿入や削除がランダムに行われたとすると、各ノードは平均3/4まで埋まっている計算になる。
リストのパラメータを
とすると、n個の要素を格納するために消費される領域のサイズは ( v + s m ) ⌈ n / m ⌉ {\displaystyle (v+sm)\lceil n/m\rceil } (おおよそ ( v / m + s ) n {\displaystyle (v/m+s)n} )からその2倍の間となる。これと比較として、通常の連結リストで消費される領域は(vは一般に小さいとしても) ( v + s ) n {\displaystyle (v+s)n} であり、また最もコンパクトなデータ構造である配列の場合は s n {\displaystyle sn} の領域を必要とする。