スキップリストとは

スキップリストとは、整列済みの連結リストに、要素をいくつか飛ばしてたどれる上位のリンクを確率的に重ねたデータ構造である。上位のリンクから順に探すことで、平均O(log n)で探索・挿入・削除ができ、平衡木より実装が簡単とされる。