スキップリスト
上で述べられているように、スキップリストでは、データ系列への値の挿入や削除は高速に( O ( log  n ) {\displaystyle {\mathcal {O}}(\log n)} で)可能であるが、系列の中のある指定した場所の値の取り出し(例えば、500番目の値を返す)は遅く、 O ( n ) {\displaystyle {\mathcal {O}}(n)} の時間がかかる。しかし、少し変更を加えることで、ランダムアクセス の実行時間は O ( log  n ) {\displaystyle {\mathcal {O}}(\log n)} にまで改良することができる。
すべてのリンクに対し、リンクの「幅」も格納することにする。ここでリンクの「幅」とは、「急行列車」のリンクが飛ばす(最下層での)リンクの数である。
例として、上で挙げた例のリンクの幅を次に示す。
第2層以上のリンクの幅は、そのリンクの下にある、下位層のリンク幅の和に等しいことに注意。(例えば、最上位層のリンク幅10は、そのすぐ下にある3つのリンクの幅 3、2、5の和になっている。