skip list in java

Question

can someone please explain the implementation of skip list in java especially insert method/function?

Answer 1

Hello THE_MASTERMIND
Can you share a code or link please so I can see it?

Answer 2

can someone help me with insert and delete

Answer 3

skipList.java

import java.util.Random;

@SuppressWarnings("unchecked")
public class SkipList<T extends Comparable<? super T>>
{

public int maxLevel;
public SkipListNode<T>[] root;
private int[] powers;
private Random rd = new Random();

SkipList(int i)
{
maxLevel = i;
root = new SkipListNode[maxLevel];
powers = new int[maxLevel];
for (int j = 0; j < i; j++)
root[j] = null;
choosePowers();
rd.setSeed(1230456789);
}

SkipList()
{
this(4);
}

public void choosePowers()
{
powers[maxLevel-1] = (2 << (maxLevel-1)) - 1;
for (int i = maxLevel - 2, j = 0; i >= 0; i--, j++)
powers[i] = powers[i+1] - (2 << j);
}

public int chooseLevel()
{
int i, r = Math.abs(rd.nextInt()) % powers[maxLevel-1] + 1;
for (i = 1; i < maxLevel; i++)
{
if(r < powers[i])
return i-1;
}
return i-1;
}

skipListNode.java

public class SkipListNode<T>
{

public T key;
public SkipListNode<T>[] next;

@SuppressWarnings("unchecked")
SkipListNode(T i, int n)
{
key = i;
next = new SkipListNode[n];

for (int j = 0; j < n; j++)
next[j] = null;
}

}

Answer 4

THE_MASTERMIND I try to take a closer look at the weekend.