当前位置：首页 > JavaScript

跳表实现 js

2026-03-02 07:32:58JavaScript

跳表实现 JavaScript

跳表（Skip List）是一种概率性的数据结构，允许快速查询、插入和删除操作，时间复杂度为O(log n)。以下是JavaScript实现跳表的方法：

定义节点类

每个节点包含值、指向下一个节点的指针数组以及节点的层级。

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

跳表类实现

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

跳表实现 js

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

随机层级生成

插入节点时随机生成层级，确保跳表的平衡性。

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

查找操作

从最高层开始查找，逐步向下缩小范围。

跳表实现 js

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

插入操作

找到插入位置并更新各层指针。

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.next[i] !== null && current.next[i].value < value) {
      current = current.next[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 Node(value, level);
  for (let i = 0; i < level; i++) {
    newNode.next[i] = update[i].next[i];
    update[i].next[i] = newNode;
  }
}

删除操作

找到目标节点并更新各层指针。

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.next[i] !== null && current.next[i].value < value) {
      current = current.next[i];
    }
    update[i] = current;
  }

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

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

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

示例用法

创建跳表实例并执行操作。

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