当前位置：首页 > JavaScript

JS实现跳表

2026-04-03 19:43:16JavaScript

跳表简介

跳表（Skip List）是一种基于概率的平衡数据结构，允许快速查询、插入和删除操作，时间复杂度为O(log n)。它通过多层链表实现，每一层都是下一层的子集，高层链表跳过多个节点以加速搜索。

跳表节点定义

使用JavaScript类定义跳表节点，包含值、指向下一个节点的指针数组（forward）：

JS实现跳表

class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level).fill(null);
  }
}

跳表类结构

跳表类需初始化最大层数、概率因子（通常0.5）、当前层数和头节点：

class SkipList {
  constructor(maxLevel = 16, probability = 0.5) {
    this.maxLevel = maxLevel;
    this.probability = probability;
    this.currentLevel = 1;
    this.head = new SkipListNode(null, maxLevel);
  }

  randomLevel() {
    let level = 1;
    while (Math.random() < this.probability && level < this.maxLevel) {
      level++;
    }
    return level;
  }
}

插入操作

插入时需要从最高层开始查找，记录每层的插入位置，随机生成新节点层数后更新指针：

JS实现跳表

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

  for (let i = this.currentLevel - 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.currentLevel) {
    for (let i = this.currentLevel; i < level; i++) {
      update[i] = this.head;
    }
    this.currentLevel = 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;
  }
}

搜索操作

从最高层开始逐层向下搜索，直到找到目标值或确认不存在：

search(value) {
  let current = this.head;
  for (let i = this.currentLevel - 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;
}

删除操作

类似插入操作，需先定位节点位置，然后逐层更新指针：

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

  for (let i = this.currentLevel - 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) {
    for (let i = 0; i < this.currentLevel; i++) {
      if (update[i].forward[i] !== current) break;
      update[i].forward[i] = current.forward[i];
    }
    while (this.currentLevel > 1 && this.head.forward[this.currentLevel - 1] === null) {
      this.currentLevel--;
    }
    return true;
  }
  return false;
}

复杂度分析

空间复杂度：O(n)，最坏情况下每层都存储所有节点。
时间复杂度：
- 搜索/插入/删除：平均O(log n)，最坏O(n)。
优势：实现比平衡树简单，适合并发操作。

完整示例

const skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
console.log(skipList.search(6)); // 返回节点
skipList.delete(6);
console.log(skipList.search(6)); // null

通过调整maxLevel和probability可平衡性能与内存消耗。实际应用中可结合具体场景优化参数。

标签: JS