使用JavaScript实现SkipList这种数据结构

代码的实现参考了SkipList.java

前言

为什么想到使用JavaScript把跳表这种数据结构来实现一遍呢？这个主要是因为我女朋友最近在学习数据结构和算法，然后遇到了这个问题；非要拉着我跟她一起 来研究一下，然后，然后就有了下面的文章。这种数据结构在Redis中使用的比较多，有兴趣的朋友可以看看。

SkipList的具体实现

首先我们先粗略的看一下JavaScript版本的代码，具体如下所示：

/**
 * author dreamapplehappy
 */

// 代码使用了ES6以及更高版本的JavaScript来表示，需要使用Babel之类的工具处理一下才可以在Node或者浏览器中运行

// 定义了跳表索引的最大级数
const MAX_LEVEL = 16;

/**
 * 定义Node类，用来辅助实现跳表功能
 */
class Node{
  // data属性存放了每个节点的数据
  data = -1;
  // maxLevel属性表明了当前节点处于整个跳表索引的级数
  maxLevel = 0;
  // refer是一个有着MAX_LEVEL大小的数组，refer属性存放着很多个索引
  // 如果用p表示当前节点，用level表示这个节点处于整个跳表索引的级数；那么p[level]表示在level这一层级p节点的下一个节点
  // p[level-n]表示level级下面n级的节点
  refer = new Array(MAX_LEVEL);
}

/**
 * 定义SkipList类
 */
class SkipList{
  // levelCount属性表示了当前跳表索引的总共级数
  levelCount = 1;
  // head属性是一个Node类的实例，指向整个链表的开始
  head = new Node();

  // 在跳里面插入数据的时候，随机生成索引的级数
  static randomLevel() {
	let level = 1;
	for(let i = 1; i < MAX_LEVEL; i++) {
	  if(Math.random() < 0.5) {
		level++;
	  }
	}
	return level;
  }

  /**
   * 向跳表里面插入数据
   * @param value
   */
  insert(value) {
	const level = SkipList.randomLevel();
	const newNode = new Node();
	newNode.data = value;
	newNode.maxLevel = level;
	const update = new Array(level).fill(new Node());
	let p = this.head;
	for(let i = level - 1; i >= 0; i--) {
	  while(p.refer[i] !== undefined && p.refer[i].data < value) {
		p = p.refer[i];
	  }
	  update[i] = p;
	}
	for(let i = 0; i < level; i++) {
	  newNode.refer[i] = update[i].refer[i];
	  update[i].refer[i] = newNode;
	}
	if(this.levelCount < level) {
	  this.levelCount = level;
	}
  }

  /**
   * 查找跳表里面的某个数据节点，并返回
   * @param value
   * @returns {*}
   */
  find(value) {
	if(!value){return null}
	let p = this.head;
	for(let i = this.levelCount - 1; i >= 0; i--) {
	  while(p.refer[i] !== undefined && p.refer[i].data < value) {
		p = p.refer[i];
		// 标记1，此处用于文章的说明
	  }
	}

	if(p.refer[0] !== undefined && p.refer[0].data === value) {
	  return p.refer[0];
	}
	return null;
  }

  /**
   * 移除跳表里面的某个数据节点
   * @param value
   * @returns {*}
   */
  remove(value) {
	let _node;
	let p = this.head;
	const update = new Array(new Node());
	for(let i = this.levelCount - 1; i >= 0; i--) {
	  while(p.refer[i] !== undefined && p.refer[i].data < value){
		p = p.refer[i];
	  }
	  update[i] = p;
	}

	if(p.refer[0] !== undefined && p.refer[0].data === value) {
	  _node = p.refer[0];
	  for(let i = 0; i <= this.levelCount - 1; i++) {
		if(update[i].refer[i] !== undefined && update[i].refer[i].data === value) {
		  update[i].refer[i] = update[i].refer[i].refer[i];
		}
	  }
	  return _node;
	}
	return null;
  }

  // 打印跳表里面的所有数据
  printAll() {
	let p = this.head;
	while(p.refer[0] !== undefined) {
	  // console.log(p.refer[0].data)
	  p = p.refer[0];
	}
  }
}

如果你看完上面的代码，感觉还是没有太明白；也不要着急，下面我会仔细的讲解一下上面代码的思路

首先，我们定义了一个Node类；这个类生成的实例有三个属性，分别是data，maxLevel和refer； 具体的解释可以看代码里面的注释；这里要注意的是refer这个属性，它是一个长度为MAX_LEVEL的数组， 数组里面的值是一个指向别的节点的索引。可以大概看下面这张图来加深一下理解：

不知道上面的图大家有没有看得更明白一点，如果没有的话，也没有关系；我们先继续往下面走。

接下来，我们又定义了一个SkipList类，这个类就是我们要实现的跳表类；SkipList的实例属性有levelCount和head 关于这两个属性的解释可以看代码里面的注释；

我们先来看一下randomLevel这个类的静态方法，这个方法用来生成一个不大于MAX_LEVEL的值；这个值 可以在我们向SkipList添加元素的时候，生成一个随机的索引级数；这个随机函数这样设计的原因是为了保证 我们在向SkipList添加元素的时候，每一级索引节点的数量大概能够是上一级索引节点的2倍。

我们首先来看一下SkipList的find方法，如果这个方法你能够理解的话，那么SkipList的remove和insert 方法你都能够快速的理解；我们来试一试吧。

首先我们把整个链表的头指针赋值给p(这里你可能会有疑问，为什么this.head就是整个链表的头指针；这个我们会在后面 讲解insert方法的时候再给大家讲解一下)。然后是两层循环，外层是一个for循环，里面是一个while循环； 我们这个时候就可以看下面这张图了：

首先我们需要知道的是，for循环是从SkipList的顶层索引开始循环，方向是从上到下的；while循环则是从某一层的索引开始， 然后从左到右循环；当然我们说的从上到下和从左到右，都是对照我们上面的那张图来进行说明的。

假设我们的SkipList是上面的那张图表示的那样，我们现在需要查找数值9；我们应该怎么做呢？看一下我们上面的代码。

我们首先从顶层开始遍历，看上面的图我们知道这个时候SkipList的levelCount应该是4，因为我们是从0开始计算索引的级数(第0级索引也就是我们的原始链表)， 所以最顶层的索引的级数应该是levelCount - 1也就是3，然后我们就进入了一个while循环，这个while循环的终止条件是： 当前节点在本层级的下一个节点(我们用p1表示)不为空(undefined)，并且p1的data值要小于我们所找的数值。

我们用l表示当前索引的级数，用p表示当前遍历到的节点(或者可以理解为一个指针)， 那么当l=3的时候，第一次while循环，p.refer[3]表示的是第三级索引的Node(1)，因为满足while的循环条件， 我们又进行一次操作，p = p.refer[i]，这表明我们此时遍历到了Node(1)，或者说是当前的指针指向了Node(1)； 然后我们准备进行下一次循环，但是p.refer[i] !== undefined && p.refer[i].data < value这个表达式的值不为真； 因为此时p表示的是Node(1)，p.refer[i]表示的是Node(15)，因为p.refer[i].data大于9，所以内部的while循环终止。

此时外层的for循环让i变为了2，然后p.refer[i]表示的是第二级索引上面的Node(1)，满足while循环，然后继续进行， 这里就不在继续描述程序的运行了，我们可以知道，当p表示的是第0级索引的Node(6)的时候，所有的循环都已经结束。

然后我们还需要进行一次判断，那就是我们当前位置的下一个节点是不是我们需要找的值(为什么还需要判断？因为我们循环的条件是当前节点 的下一个节点的data值要小于我们查找的value，如果循环结束，那说明当前节点的下一个节点的值大于或者等于value值，所以还需要进行以此判断)。 如果是的话，就返回p.refer[i]，如果不是就返回一个null。

我们可以用下面这个表格来表示上面的描述，表格表示的是代码中find函数里面注释的标记1，这个表格的表示应该更直观一些吧。

如果上面的描述你都理解的话，那么SkipList的insert和remove方法你应该很快就明白了； 这两个方法我们就不再像上面那样详细的讲解了；我们会大概的说明一下实现的原理。

关于insert方法，在插入一个数据的时候，我们首先生成一个随机的level值，用来表示这个数据索引的级数； 然后我们生成一个新的节点newNode，接下来我们创建一个update数组，这个数组的长度是level； 里面存放的是一些节点。

接下来就是熟悉的两层循环，通过上面的那个表格我们可以看到，update数组里面保存的就是 每次while循环终止的那个节点，就是上面图片3中紫色线框框起来的节点；然后我们又运行了一个for循环， 接下来的代码很有技巧，我们把新的节点的refer[i](i表示的是索引的级数)指向下一个节点，然后把update[i]节点的refer[i]指向新的节点 当循环完成的时候，我们就把这个数据插入到了原来的SkipList当中。更清晰直观的过程可以看下面的图片。

然后，我们还需要看一下当前的level是否大于SkipList的最大级数也就是levelCount，如果大于当前的levelCount， 我们还需要更新SkipList的levelCount。

关于remove方法，这个方法其实和remove方法很相似了；不同点在于，我们首先需要找到要删除的元素； 如果这个元素在SkipList中不存在的话，我们不能够进行删除的操作； 只有这个元素在SkipList中存在的话，我们才能够进行删除操作； 所谓的删除也就是把P(pre)的索引指向P(next) (其中P(pre)表示位于同一级别索引的P节点的上一个节点，P(next)表示位于同一级别索引的P节点的下一个节点)， 这样我们就把这个节点删除掉了；下面的图形象地表示了这一个过程。

最后说一下printAll方法，这个方法就是打印出我们在SkipList存储的所有数据；因为第0级索引存放的就是 我们的原始数据。到这里为止，关于代码部分我们已经讲解完毕了。

测试SkipList相关操作的效率

接下来我们来测试一下SkipList相关操作的效率，具体的代码可以看这个文件，我们直接把测试的结果用下面的表格来进行表示：

浏览器环境下：

Node环境下：

如果大家要进行测试的话，要注意一点；当操作的数据样本数量为100000的时候，因为生成SkipList需要比较长的时间，所以可能要稍稍等一下。

通过上面的表格我们可以看到，使用SKipList的效率是很高的。到这里整篇文章也就算结束啦，文章中可能会有不严谨的地方，也欢迎大家指出来，我们一起共同进步。

如果你有什么想说的，可以在这里发表评论.