【スキップリスト】
スキップリスト とは？
💡 急行・快速・各停の多段express！リンクリストの高速化テクニック
📌 このページのポイント
ひよこ スキップリストって普通のリンクリストと何が違うの？
ペンギン先生 普通のリンクリストは先頭から1つずつたどるから検索にO(n)かかる。スキップリストは「快速電車」みたいに、いくつか飛ばして進めるリンクが何段もあるんだ。急行→快速→各停と乗り換えるイメージだよ
ひよこ でもどの要素に飛ばしリンクを付けるか、どうやって決めるの？
ペンギン先生 ここが面白いところで、コイントスのようにランダムに決めるんだ。「表が出たらもう1段上のレベルにも登録」を繰り返す。確率的に均等な間隔になるから、平均O(log n)の性能が出るんだよ
ひよこ ランダムで大丈夫なの？偏ったりしない？
ペンギン先生 ひよこ 実際にどこで使われてるの？
ペンギン先生 ひよこ 平衡二分木より良いことってあるの？
ペンギン先生 ロックフリーの並行処理に向いているのが大きいね。木の回転操作は複数ノードを同時に変更する必要があるけど、スキップリストはポインタの付け替えだけで済むから、マルチスレッド環境で有利なんだよ
まとめ：ざっくりこれだけ覚えればOK！
「スキップリスト」って出てきたら「飛ばしリンク付きのリストで高速検索できる仕組み」と思えればだいたいOK！
📖 おまけ：英語の意味
「Skip List」 ＝ 飛ばしリスト
💬 Skip（飛ばす）の名の通り、要素を飛ばしながら目的地に素早くたどり着くリストだよ。1990年にWilliam Pughが発表した比較的新しいデータ構造だよ