classSkipList{ // special// special val negInf = "-infinity" val posInf = "+infinity" var head:SkipListEntry = null// First element of the top level var tail:SkipListEntry = null// Last element of the top level var n = 0// number of entries in the Skip List var h = 0// Height var r = newRandom() // Coin toss
// constructor defthis(capcity:Int){ this() var p1: SkipListEntry = null var p2: SkipListEntry = null
privatedeffindEntry(key: String) : SkipListEntry ={ var p:SkipListEntry = null // 从head头节点开始查找 p = head while (true){ // 从左向右查找,直到右节点的key值大于要查找的key值 while ((p.right.key ne posInf) && p.right.key.compareTo(key) <= 0) { p = p.right } // 如果有更低层的节点,则向低层移动 if (p.down != null) { p = p.down }else{ return p } //todo: break is not supported } // 返回p,!注意这里p的key值是小于等于传入key的值的(p.key <= key) return p }
defput(key: String, value: Integer): Integer = { var p:SkipListEntry = null var q:SkipListEntry = null var i = 0 // 查找适合插入的位子 p = findEntry(key) // 如果跳跃表中存在含有key值的节点,则进行value的修改操作即可完成 if (p.key.equals(key)) { val oldValue = p.value p.value = value return oldValue } // 如果跳跃表中不存在含有key值的节点,则进行新增操作 q = newSkipListEntry(key, value) q.left = p q.right = p.right p.right.left = q p.right = q // 再使用随机数决定是否要向更高level攀升 while (r.nextDouble < 0.5) { // 如果新元素的级别已经达到跳跃表的最大高度,则新建空白层 if (i >= h) { addEmptyLevel() } // 从p向左扫描含有高层节点的节点 while (p.up == null) { p = p.left } p = p.up // 新增和q指针指向的节点含有相同key值的节点对象 // 这里需要注意的是除底层节点之外的节点对象是不需要value值的 val z = newSkipListEntry(key, null) z.left = p z.right = p.right p.right.left = z p.right = z z.down = q q.up = z q = z i = i + 1 } n = n + 1 // 返回null,没有旧节点的value值 null }
privatedefaddEmptyLevel(): Unit = { val p1 = newSkipListEntry(negInf, null) val p2 = newSkipListEntry(posInf, null) p1.right = p2 p1.down = head p2.left = p1 p2.down = tail head.up = p1 tail.up = p2 head = p1 tail = p2 h = h + 1 }
defget(key: String): Integer = { var p = findEntry(key) if (p.key.equals(key)) p.value elsenull } }
package lishijia.algorithm.skiplist /** * skipList数据存储结构 */ classSkipListEntry{ // data var key:String = null var value:Integer = null // links var up:SkipListEntry = null var down:SkipListEntry = null var left:SkipListEntry = null var right:SkipListEntry = null defthis(key: String, value: Integer){ this() this.key=key this.value=value } }