以空间换时间，时间复杂度 O(logN)，空间复杂度 O(n)

和平衡二叉树相比，跳表在按区间查询上效率更高。

跳表动态插入与删除

如果这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点。当然，如果我们用的是双向链表，就不需要考虑这个问题了。

跳表索引动态更新

当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。

跳表中通过随机函数来维护各个索引之间的“平衡性”。

当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？

我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

// 以下是一个 random_level 案例
void random_init()
{
	static bool done = false;

	if (done)
		return;

	srandom(time(NULL));
	done = true;
}

int random_level(void)
{
  int i, level = 1;

  random_init();

  for (i = 1; i < MAX_LEVEL; i++)
    if (random() % 2 == 1)
	    level++;

  return level;
}