Implement a skip list class in Java.

Use randomization to promote nodes to higher levels. Implement the following methods: skipInsert(k,v) to insert in a skip list entry with key k and value v;

skipRemove(k) to remove position corresponding to key k from all levels in the skipList;

skipSearch(k) to search for key k in the skip list (returns position corresponding to key k in the bottom list,

1 or null if k is not found). The java file should include the main method that creates a

skip list from the hardcoded sequence of 10 integers and prints out the resulting list to

stdout.

Please do not post an answer if you cannot fully answer the question and the code must compile and run. You must implement the main method so that the code can be executed.

Use the folllowing algorithms to implement the functions

Algorithm SkipSearch(k):

Input: A search key k

Output: Position p in the bottom list S0 with the largest key having key(p) k

p = s {begin at start position}

while below(p) 6= null do

p = below(p) {drop down}

while k key(next(p)) do

p = next(p) {scan forward}

return p

---------------------------------------------------------

Algorithm SkipInsert(k, v):

Input: Key k and value v

Output: Topmost position of the entry inserted in the skip list

p = SkipSearch(k) {position in bottom list with largest key less than k}

q = null {current node of new entrys tower}

i = 1 {current height of new entrys tower}

repeat

i = i +1 {increase height of new entrys tower}

if i h then

h = h +1 {add a new level to the skip list}

t = next(s)

s = insertAfterAbove(null, s, (,null)) {grow leftmost tower}

insertAfterAbove(s, t, (+,null)) {grow rightmost tower}

q = insertAfterAbove(p, q, (k,v)) {add node to new entrys tower}

while above(p) == null do

p = prev(p) {scan backward}

p = above(p) {jump up to higher level}

until coinFlip( ) == tails

n = n +1

return q {top node of new entrys tower}

--------------------------------------------------------------

To perform the map operation remove(k), begin by executing method SkipSearch(k). If the returned position p stores an entry with key different from k, return null. Otherwise, remove p and all the positions above p, which are easily accessed by using above operations to climb up the tower of this entry in S starting at position p. While removing levels of the tower, reestablish links between the horizontal neighbors of each removed position.