当前位置：首页 > JavaScript

JS实现跳表

2026-02-28 19:17:59JavaScript

跳表（Skip List）简介

跳表是一种基于概率的平衡数据结构，通过多层链表实现高效查找、插入和删除操作，时间复杂度为 $O(\log n)$。其核心思想是通过“跳跃”式访问节点减少遍历次数。

跳表节点结构

跳表节点包含值（value）和指向后续节点的指针数组（forward）。每一层对应一个指针，用于在不同层级间跳跃。

class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level).fill(null); // 初始化各层指针为null
  }
}

跳表类实现

跳表类需初始化头节点、最大层级和概率因子（通常为0.5）。

class SkipList {
  constructor() {
    this.maxLevel = 16; // 最大层数
    this.head = new SkipListNode(null, this.maxLevel); // 头节点
    this.level = 1; // 当前有效层数
    this.p = 0.5; // 概率因子
  }

  // 随机生成节点层数
  randomLevel() {
    let level = 1;
    while (Math.random() < this.p && level < this.maxLevel) {
      level++;
    }
    return level;
  }
}

查找操作

从最高层开始查找，逐步向下直至找到目标或确认不存在。

search(value) {
  let current = this.head;
  for (let i = this.level - 1; i >= 0; i--) {
    while (current.forward[i] && current.forward[i].value < value) {
      current = current.forward[i];
    }
  }
  current = current.forward[0];
  return current && current.value === value ? current : null;
}

插入操作

确定插入位置并记录每层的前驱节点。
随机生成新节点层数，更新前驱节点的指针。

insert(value) {
  const update = new Array(this.maxLevel).fill(null);
  let current = this.head;

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

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

  const newNode = new SkipListNode(value, level);
  for (let i = 0; i < level; i++) {
    newNode.forward[i] = update[i].forward[i];
    update[i].forward[i] = newNode;
  }
}

删除操作

类似插入，需先定位节点并更新前驱指针。

JS实现跳表

delete(value) {
  const update = new Array(this.maxLevel).fill(null);
  let current = this.head;

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

  current = current.forward[0];
  if (!current || current.value !== value) return false;

  for (let i = 0; i < this.level; i++) {
    if (update[i].forward[i] !== current) break;
    update[i].forward[i] = current.forward[i];
  }

  while (this.level > 1 && !this.head.forward[this.level - 1]) {
    this.level--;
  }
  return true;
}