スキップリスト
)したがって、すべての層において、すべてのリンクの幅の和は等しい (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5)。
スキップリストにインデクスをつけて i 番目の値を探すには、スキップリスト内を、進んだリンクの幅の分だけ必要ステップ数を減らしながら、リンクを辿っていけばよい。次のリンク幅が大きすぎる場合には、下の層へ降りる。
例えば、上の例で5番目の値を得たい場合には、まず最上位層の幅1のリンクを進む。残りの必要ステップ数は 4=5-1 であるが、次のステップ幅は10であり大きすぎるので、第3層へ降りる。この層で、幅3のリンクを進む。 残りの必要ステップ数は1で、次のリンク幅は2のため大きすぎ、下の層へ降りる。第2層の次のリンクも幅が2で大きすぎるため、最下層に降りる。最後に幅1のリンクを1つ進めば、5(=1+3+1)ステップ進んだことになり、目的のノードにたどり着く。
このインデクス付けの実装方法については、Section 3.4 Linear List Operations in "A skip list cookbook" by William Pughに詳細がある。
スキップグラフとは、スキップリストを元に、P2Pネットワーク環境を想定した分散データ構造。スキップリスト上の1つのノードが1つのマシンに対応し、連結を双方向連結リストにする。2003年に James Aspnes らが発表した。
スキップリスト(英: skip list)は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した。
スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され(高さ1が確率50%、高さ2が25%、高さ3が12.5%など)、リスト上の探索において連結リストの一部を高速に飛ばすことができる。