当前位置：首页 > JavaScript

跳表js实现

2026-03-13 22:06:29JavaScript

跳表（Skip List）的 JavaScript 实现

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

跳表节点类

定义跳表节点的结构，包含值、层级指针数组和层级高度：

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

跳表类

实现跳表的主要逻辑：

跳表js实现

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

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

插入操作

实现元素的插入逻辑：

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

  current = current.forward[0];
  if (current === null || current.value !== value) {
    const newLevel = this.randomLevel();
    if (newLevel > this.level) {
      for (let i = this.level; i < newLevel; i++) {
        update[i] = this.head;
      }
      this.level = newLevel;
    }

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

搜索操作

实现元素的查找逻辑：

跳表js实现

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

删除操作

实现元素的删除逻辑：

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

  current = current.forward[0];
  if (current !== null && current.value === value) {
    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] === null) {
      this.level--;
    }
    return true;
  }
  return false;
}

使用示例

创建跳表实例并测试功能：

const skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
skipList.insert(9);
console.log(skipList.search(6)); // true
console.log(skipList.search(8)); // false
skipList.delete(6);
console.log(skipList.search(6)); // false