跳表

一、链表的缺点

链表在查找元素的时候，因为需要逐一查找，所以查询效率非常低，时间复杂度是O(N)

二、跳表的优势

跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表。本质就是抽取链表中部分节点充当索引，加快查询。

图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

L0 层级共有 5 个节点，分别是节点1、2、3、4、5； L1 层级共有 3 个节点，分别是节点 2、3、5； L2 层级只有 1 个节点，也就是节点 3 。 如果我们要在链表中查找节点 4 这个元素，只能从头开始遍历链表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再往前遍历找到节点 4。

可以看到，这个查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度就是 O(logN)。