跳表(skip list)

跳表是通过链表来存储有序数组，查找、插入、删除数据非常高效。代码如下(kotlin编写)：

class SkipList {

    companion object {
        //跳表的最大高度
        const val MAX_LEVEL = 16
    }

    /**
     * 这里使用带头链表，方便操作
     *
     * head            7                    //第2层索引
     * head      3     7     11             //第1层索引
     * head   1  3  5  7  9  11  13  15     //第0层，原始链表
     *
     * 对于 head 节点，nextNodes[0] = 1，nextNodes[1] = 3，nextNodes[2] = 7
     * 对于节点 3，nextNode[0] = 5，nextNodes[1] = 7，nextNodes[2] = null
     */
    class Node {
        //只存储非负整数
        var data: Int = -1
        //通过数组来存储该节点在每层索引上的下一个节点指针
        //nextNodes[0] 表示该节点在原始链表上的下一个节点指针
        //nextNodes[1] 表示该节点在第1层索引上的下一个节点指针
        //nextNodes[2] 表示该节点在第2层索引上的下一个节点指针，依次类推，直到 nextNodes[MAX_LEVEL - 1]
        var nextNodes: Array<Node?> = arrayOfNulls(MAX_LEVEL)

        override fun toString(): String {
            return "data: $data"
        }
    }

    //带头链表，为了放标操作，其实不存储任何实际数据
    private var head = Node()

    //当前跳表的实际层数，刚开始为 1
     var levelCount = 1

    /**
     * 查找节点
     */
    fun find(value: Int): Node? {
        //从最上面的索引开始查找，从上往下，一直到原始链表上查找
        var p = head
        for (i in levelCount - 1 downTo 0) {
            while (p.nextNodes[i] != null && (p.nextNodes[i]!!.data) < value) {
                p = p.nextNodes[i]!!
            }
        }
        return if (p.nextNodes[0]?.data == value) p.nextNodes[0] else null
    }

    /**
     * 插入数据
     */
    fun insert(value: Int) {
        var level = randomLevel()
        var newNode = Node()
        newNode.data = value

        //定义一个数组，保存每层索引待插入节点的前置节点
        var update = Array(level) { head }
        var p = head
        for (i in level - 1 downTo 0) {
            while (p.nextNodes[i] != null && p.nextNodes[i]!!.data < value) {
                p = p.nextNodes[i]!!
            }
            update[i] = p
        }

        //每层索引插入新节点
        for (i in update.indices) {
            newNode.nextNodes[i] = update[i].nextNodes[i]
            update[i].nextNodes[i] = newNode
        }

        if (levelCount < level) levelCount = level
    }

    fun delete(value: Int) {
        //同样先找到待删除节点的前置节点
        var update = arrayOfNulls<Node>(levelCount)
        var p = head
        for (i in levelCount - 1 downTo 0) {
            while (p.nextNodes[i] != null && p.nextNodes[i]!!.data < value) {
                p = p.nextNodes[i]!!
            }
            update[i] = p
        }

        //先如果能找到节点
        if (p.nextNodes[0]?.data == value ) {
            for (i in update.indices) {
                //前置节点的下一节点与待删除数据相等，则需要更新链表
                var updateNode = update[i]
                if (updateNode != null && updateNode.nextNodes[i] != null && updateNode.nextNodes[i]!!.data == value) {
                    updateNode.nextNodes[i] = updateNode.nextNodes[i]!!.nextNodes[i]
                }
            }
        }

        while (levelCount > 1 && head.nextNodes[levelCount - 1] == null) {
            levelCount--
        }
    }

    /**
     * 随机返回 [1, MAX_LEVEL] 之间的数
     */
    private fun randomLevel(): Int {
        var level = 1
        while (Math.random() < 0.5 && level < MAX_LEVEL) {
            level++
        }
        return level
    }
}

查找时间复杂度：O(logn)
插入时间复杂度：O(logn)
删除时间复杂度：O(logn)
空间复杂度为O(n)，如果跳表存储的是一些大对象数据，那么相对于这些数据来说，额外需要的存储空间并不大。