当前位置：首页 > JavaScript

JS实现跳表

2026-01-14 13:58:13JavaScript

跳表的基本概念

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

跳表的实现步骤

定义节点类 每个节点包含值、指向下一个节点的指针数组（用于多层链表）：

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

初始化跳表 设置最大层数和概率因子（通常为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;
  }
}

插入操作

生成新节点的随机层数
从最高层开始查找插入位置

更新各层指针：


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; } }


搜索操作
从最高层开始逐层向下搜索：
```javascript
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; }


### 复杂度分析
- 空间复杂度：O(n)，最坏情况下每个节点可能包含maxLevel个指针
- 时间复杂度：
  - 搜索/插入/删除：平均O(log n)，最坏O(n)
  - 随机层数生成：O(log n)

### 实际应用建议
1. 调整maxLevel和p值可平衡性能与内存使用
2. 适合需要快速查找且数据动态变化的场景
3. 可作为平衡树的替代方案，实现更简单

### 完整示例代码
```javascript
// 完整类实现（包含上述所有方法）
class SkipList {
  // 构造函数和上述方法...
}

// 使用示例
const list = new SkipList();
list.insert(3);
list.insert(6);
list.insert(7);
console.log(list.search(6)); // 返回节点
list.delete(6);
console.log(list.search(6)); // null

JS实现跳表