スキップリスト
偶数ならば直前のノードの高さが2になっていないときのみ高さを2にする。高くなったノードの数が2以上なら高さを上げてこれを繰り返す。 ランダム性の削除と同様に、この擬似的なランダマイズはノードを全て訪れる場合にのみ実行する。
擬似的なランダマイズを行う利点は、ランダム性の無い場合と違い、敵意のあるユーザーに高さに関する情報を漏らさないことである。悪意あるユーザが高さに関する情報を知っていると、レベルの高いノードを削除するだけで性能を悪化させことができるため、この性質は望ましい。(これに対し、BetheaとReiterは、悪意あるユーザが性能劣化を起こすために、確率的タイミング方法を使用できると主張している。) 検索時間については、ランダム性の無い場合と同様、対数時間であることが保証されている。
以下の「最適化」を考えてみよう。「次に, 各i番目のノードに対して・・・」の部分で、各奇数と偶数のペアに対するコイン投げをするのをやめ、その替わり、コインを1回だけ振って、全てのペアに対して偶数番目のノードの高さを上げるか、あるいは奇数の方の高さを上げるかを決める。
もし、探し出した要素が目的の要素より大きいならば、あるいは、リストの最後の要素に到達してしまった場合は、一つ前の要素に戻ってから一つ下の層の連結リストに(垂直方向に)降り、そのリストに対して同じ操作を繰り返す。各連結リストにおいてリンクを辿る数の期待値は最大でも 1/p となる。これは目的の要素から逆向きに戻って上層のリストにつながる要素に到達するまでの期待値であることから理解できる。従って探索の総コストは ( log 1 / p  n ) / p {\displaystyle (\log _{1/p}n)/p\,} で、pを固定すれば O ( log  n ) {\displaystyle {\mathcal {O}}(\log n)\,} である。pにさまざまな値を選ぶことで、探索時間とメモリ使用量のトレードオフをとることが可能である。