每个程序员都应该掌握的数据结构 – Skip List

Skip List

这种数据结构翻译成中文，大家一般叫它跳表，非常直译，其实我接触这种数据结构比较早，但是看很多技术分享的时候一直听到有人说跳表，跳表，但我始终没有把它和skip list联系起来。

Skip List也是链表的一种变形，同样是在node结构上做文章，它的出发点非常简单直接，因为一个有序数组我们支持二分查找，那么一个有序链表我们是不是也能支持类似的快速查找呢？于是跳表就出现了，它是典型的空间换时间的一个具体实现，下图引用自Skip List

skip list

每个节点都有一个指针数组指向不同的节点，在每一层上看都是一个节点有序的链表，其实也有一些实现是基于unrolled list的，就在每个节点维护一个有序数组，但是那种方式牵涉到每个节点需要维护多少个值的问题，也是需要在实际的环境中去调优的，说远了，还是回到跳表实现的本身，我们需要注意的是一般跳表的实现在查找的时候都不能保证二分查找，要完美支持二分查找的话，跳表的实现复杂度相当大，而且结构的重整非常频繁，反而得不偿失，一般跳表插入元素的时候会有个随机数来表示这个节点需要扩展到多高的高度，大于这个高度的那层链表不必包含这个新增的节点，低于这个高度的链表必须包含这个节点，在插入节点后，具体要更新哪些节点的next数组的哪些位置的值可以在查找插入位置的过程中把它记下来，这些需要更新的节点数量不会超过跳表节点的最高高度，

template < typename T >

struct SkipListNode{

    SkipListNode** next; //dynamic allocate

    int length; //next array length and also is node level

    T data

}

以上。