参考資料：William Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees”
https://www.cs.umd.edu/~pugh/skiplist.pdf

本稿は上記のアイデアを TypeScript で書き直し、実装上の不変条件と境界テストを整理したものです。

TypeScriptでSkip Listを実装する：確率的な多段リンクで探索をO(log n)にする

先に結論

Skip List（スキップリスト）は、ソート済みの単方向リストに「ショートカットの層」を重ねるデータ構造です。

検索・挿入・削除：期待計算量 O(log n)
最悪計算量：O(n)
空間計算量：O(n)
実装の中心：各ノードの高さを確率的に決め、各層の直前ノードを同時に覚える

平衡二分探索木のような回転処理を使わずに、順序付き集合を実装できます。面接では「なぜ平均 O(log n) になるのか」と「削除時にどのリンクを更新するのか」を説明できると、単なるコード暗記から一歩進めます。

1. どこが速いのか

通常の単方向リストで値を探すと、先頭から一つずつ比較するため O(n) です。

Skip Listでは、ノードに複数のnextを持たせます。下の層は全要素をつなぎ、上の層は一部の要素だけをつなぎます。検索は最上層から始め、次へ進むと値を越えてしまう直前まで進み、そこで一つ下の層へ降ります。

各ノードが次の層へ昇格する確率を p = 0.5 とすると、層 l に残るノード数の期待値は n × p^(l-1) です。したがって、層を上り下りする回数の期待値は O(log n) になります。

ただし確率的な構造なので、入力によっては高さが偏ります。これは「常に O(log n)」ではなく「期待 O(log n)」と説明するのが正確です。

2. 実装で守る不変条件

実装を複雑にしないため、次の条件を固定します。

各層のリンクは値の昇順になっている。
ノードが高さ h を持つとき、next[0]からnext[h - 1]までが存在する。
上位層に存在するノードは、必ず下位層にも存在する。
headは実データではなく、すべての層の先頭を表す番兵ノードである。
levelは現在使っている最高層（1始まり）である。

挿入・削除の前に、検索と同じ経路をたどって各層の「直前ノード」をupdateに保存します。これが多段リンクを一度に更新する鍵です。

3. TypeScript実装

addは重複値を拒否する集合として実装します。重複を許したい場合は、比較条件を変更し、同値の挿入位置を仕様として決めてください。

type RNG = () => number;

type Node = {
  value: number;
  next: Array<Node | null>;
};

class SkipList {
  private readonly head: Node;
  private level = 1;

  constructor(
    private readonly maxLevel = 16,
    private readonly probability = 0.5,
    private readonly rng: RNG = Math.random,
  ) {
    if (maxLevel < 1 || probability <= 0 || probability >= 1) {
      throw new RangeError("invalid skip-list parameters");
    }
    this.head = {
      value: Number.NEGATIVE_INFINITY,
      next: Array(maxLevel).fill(null),
    };
  }

  private randomLevel(): number {
    let level = 1;
    while (level < this.maxLevel && this.rng() < this.probability) {
      level += 1;
    }
    return level;
  }

  has(value: number): boolean {
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (current.next[i] && current.next[i]!.value < value) {
        current = current.next[i]!;
      }
    }

    return current.next[0]?.value === value;
  }

  add(value: number): boolean {
    const update: Node[] = Array(this.maxLevel).fill(this.head);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (current.next[i] && current.next[i]!.value < value) {
        current = current.next[i]!;
      }
      update[i] = current;
    }

    if (update[0].next[0]?.value === value) return false;

    const nodeLevel = this.randomLevel();
    if (nodeLevel > this.level) {
      for (let i = this.level; i < nodeLevel; i += 1) {
        update[i] = this.head;
      }
      this.level = nodeLevel;
    }

    const node: Node = {
      value,
      next: Array(nodeLevel).fill(null),
    };

    for (let i = 0; i < nodeLevel; i += 1) {
      node.next[i] = update[i].next[i];
      update[i].next[i] = node;
    }
    return true;
  }

  remove(value: number): boolean {
    const update: Node[] = Array(this.maxLevel).fill(this.head);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (current.next[i] && current.next[i]!.value < value) {
        current = current.next[i]!;
      }
      update[i] = current;
    }

    const target = update[0].next[0];
    if (!target || target.value !== value) return false;

    for (let i = 0; i < this.level; i += 1) {
      if (update[i].next[i] !== target) break;
      update[i].next[i] = target.next[i] ?? null;
    }

    while (this.level > 1 && this.head.next[this.level - 1] === null) {
      this.level -= 1;
    }
    return true;
  }

  values(): number[] {
    const values: number[] = [];
    for (let current = this.head.next[0]; current; current = current.next[0]) {
      values.push(current.value);
    }
    return values;
  }
}

update配列の意味

たとえば値8を挿入する場合、update[0]は最下層で8の直前にあるノード、update[1]は第2層での直前ノードです。

新しいノードの高さが3なら、次の3本をそれぞれ差し替えます。

update[0] -> new -> update[0].next[0]
update[1] -> new -> update[1].next[1]
update[2] -> new -> update[2].next[2]

削除では逆に、対象ノードを指している層だけをつなぎ直します。対象の高さより上の層は対象を指していないので、そこでループを打ち切れます。

4. 境界を含むテスト

乱数をそのまま使うとテストが再現できないため、テストでは線形合同法の小さな疑似乱数生成器を渡します。実運用の乱数品質を評価するものではなく、構造を固定して回帰テストを再現するためのものです。

let seed = 0x12345678;
const rng = () => {
  seed = (Math.imul(seed, 1664525) + 1013904223) >>> 0;
  return seed / 0x1_0000_0000;
};

const list = new SkipList(12, 0.5, rng);
console.assert(list.values().length === 0);
console.assert(list.add(8));
console.assert(list.add(3));
console.assert(list.add(13));
console.assert(list.add(5));
console.assert(!list.add(8));
console.assert(list.has(3) && list.has(13) && !list.has(7));
console.assert(JSON.stringify(list.values()) === JSON.stringify([3, 5, 8, 13]));
console.assert(list.remove(8) && !list.has(8));
console.assert(!list.remove(8));
console.assert(JSON.stringify(list.values()) === JSON.stringify([3, 5, 13]));

const reference = new Set<number>();
const randomList = new SkipList(16, 0.5, rng);
for (let i = 0; i < 500; i += 1) {
  const value = (i * 73) % 211;
  randomList.add(value);
  reference.add(value);
}
console.assert(
  JSON.stringify(randomList.values()) ===
    JSON.stringify([...reference].sort((a, b) => a - b)),
);
console.log("skip-list tests: ok");

このテストで確認しているのは次の点です。

空のリストから開始できる
乱序で追加しても最下層は昇順になる
重複追加はfalseを返し、要素を増やさない
存在する値と存在しない値を正しく判定する
同じ値を2回削除できない
500回の追加結果が、参照実装のSetをソートした結果と一致する

実行結果：

skip-list tests: ok

5. 面接で説明するなら

「なぜ配列や通常のリンクリストではなくSkip Listを使うのですか？」

順序を保った検索・挿入・削除が必要で、平衡木の回転処理を自前で持ちたくない場合の選択肢です。実装は比較的局所的で、期待 O(log n) の性能を得られます。一方、厳密な最悪計算量の保証が必要なら、AVL木や赤黒木など別の構造を選びます。

「乱数に依存するのは危険ではありませんか？」

性能保証は期待値です。maxLevelで高さを制限し、監視対象のレイテンシやノード分布を確認します。攻撃者が乱数や入力を制御できる環境で厳密な上限が必要なら、決定的な平衡木のほうが適切です。

「削除で全層を走査する必要はありますか？」

必要ありません。検索時に各層の直前ノードをupdateへ保存しているため、対象ノードの高さまでリンクを更新できます。最後に空になった最高層をlevelから下げます。

まとめ

Skip Listの要点は、単方向リストを捨てることではなく、同じ順序を保ったまま複数の探索経路を持つことです。

下位層が正しい順序を保証する
上位層が探索距離を短くする
updateが挿入・削除の全層更新を可能にする
計算量は「最悪」ではなく「期待」と表現する
疑似乱数と参照実装で、構造と境界を再現可能に検証する

この4点をコードと一緒に説明できれば、Skip Listを知っているだけでなく、設計上のトレードオフまで理解していることを示せます。