要素の挿入、削除、ランダムアクセスが全部高速なリストを作った
スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。
Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。
で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。
通常のSkip Listでは、各ノードは次のノードへのリンクしか保持していません。ここに少し工夫を加えて、上の画像のように、次ノードまでの「距離」を持たせるようにしました。ノード探索時にこの距離を加算していくことで、indexによる要素の取得をO(logN)で実行できます。
このSkipListに加えて、java.util.Listとjava.util.Setを両方実装したSkipListSetというものも作りました。こちらは内部的にHashMapを併用していて、indexOf()やcontains()も高速になっています。各メソッドの計算量比較は以下の通りです。
| メソッド | ArrayList | SkipList | SkipListSet |
|---|---|---|---|
| get(index) | O(1) | O(logN) | O(logN) |
| set(index, element) | O(1) | O(logN) | O(logN) |
| add(element) | O(1) | O(logN) | O(logN) |
| add(index, element) | O(N) | O(logN) | O(logN) |
| remove(index) | O(N) | O(logN) | O(logN) |
| remove(element) | O(N) | O(N) | O(logN) |
| indexOf(element) | O(N) | O(N) | O(logN) |
| contains(element) | O(N) | O(N) | O(1) |
| iterator().next() | O(1) | O(1) | O(1) |
ソースは以下からどうぞ。
