当前位置：首页 > JavaScript

跳表js实现

2026-04-05 16:18:56JavaScript

跳表简介

跳表（Skip List）是一种基于概率的平衡数据结构，通过多层链表实现快速查找、插入和删除操作，时间复杂度为O(log n)。跳表常用于替代平衡树，实现简单且性能高效。

跳表节点结构

跳表节点包含值、指向下一个节点的指针数组（用于多层链表）以及节点高度。

跳表js实现

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

跳表类实现

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

class SkipList {
  constructor(maxLevel = 16, p = 0.5) {
    this.maxLevel = maxLevel;
    this.p = p;
    this.head = new SkipListNode(null, maxLevel);
    this.level = 1; // 当前有效层数
  }

  // 随机生成节点层数
  randomLevel() {
    let level = 1;
    while (Math.random() < this.p && 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.level - 1; i >= 0; i--) {
    while (current.next[i] !== null && current.next[i].value < value) {
      current = current.next[i];
    }
    update[i] = current;
  }

  // 生成新节点层数
  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.next[i] = update[i].next[i];
    update[i].next[i] = newNode;
  }
}

查找操作

查找操作从最高层开始，逐步向下层搜索目标值。

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

删除操作

删除操作需找到每一层的前驱节点，并更新链表指针。

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.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.level; i++) {
    if (update[i].next[i] !== current) break;
    update[i].next[i] = current.next[i];
  }

  // 降低跳表层数（若顶层无节点）
  while (this.level > 1 && this.head.next[this.level - 1] === null) {
    this.level--;
  }
  return true;
}

示例用法

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