########################################
跳跃链表
########################################

跳跃链表算是一种比较简单而效率又高的数据结构，它的性能如下： [#performance]_

================== =================
平均查找时间复杂度 :math:`O(\log n)`
插入时间复杂度     :math:`O(\log n)`
================== =================

.. [#performance] `深入理解跳跃链表[一] <https://zhuanlan.zhihu.com/p/91753863>`_

跳跃链表本质上就是将一维有序数组中的某些元素离散地提取出来构成第二层，多层依次递推，查找时从高层开始查，由于高层比底层更加稀疏，因此提高了查找的效率。

这里不再多说，直接引入存的笔记：

.. image:: assets/skip_list1.jpg
.. image:: assets/skip_list2.jpg
.. image:: assets/skip_list3.jpg
.. image:: assets/skip_list4.jpg