I recently studied SkipList and thought I would create one on my own. This implementation uses a 2 layer `SkipList where the size of the support list is roughly square root of the size of the original list.
package skiplists.skiplist;
public class SkipList<T extends Comparable<T>> {
private SkipNode<T> start;
private SkipNode<T> end;
private SkipNode<T> supportStart;
private SkipNode<T> supportEnd;
private int size;
private int sizeSupport;
public T getStart() {
return start.getData();
}
public T getEnd() {
return end.getData();
}
public int getSize() {
return size;
}
public void add(T data){
if(start == null){
insertAsFirstElement(data);
}
else{
insert(data);
}
}
private void insertAsFirstElement(T data){
SkipNode<T> node = new SkipNode<>(data);
start = node;
end = node;
size++;
SkipNode<T> supportNode = new SkipNode<>(data);
supportStart = supportNode;
supportEnd = supportNode;
supportNode.setDown(node);
sizeSupport++;
}
//Adding element in the end assuming user enters data in ascending order
private void insert(T data){
SkipNode<T> node = new SkipNode<>(data);
end.setNext(node);
node.setPrevious(end);
end = node;
size++;
int expectedSupportSize = (int) Math.sqrt(size);
if(sizeSupport < expectedSupportSize){
SkipNode<T> supportNode = new SkipNode<>(data);
supportEnd.setNext(supportNode);
supportNode.setPrevious(supportEnd);
supportEnd = supportNode;
supportNode.setDown(node);
sizeSupport++;
if(sizeSupport > 2)
reAjustSupportList();
}
}
/*readjusting the support list so that they point to the correct nodes when new
*support nodes are added
*/
private void reAjustSupportList(){
SkipNode<T> navigationNode = supportStart.getNext();
int i = 1;
while(navigationNode != supportEnd){
SkipNode<T> tempNode = navigationNode.getDown();
for(int j = 1 ; j <= i ; j++){
tempNode = tempNode.getNext();
}
navigationNode.setDown(tempNode);
navigationNode.setData(tempNode.getData());
navigationNode = navigationNode.getNext();
i++;
}
}
public boolean search(T data){
SkipNode<T> navigationNode = supportStart;
if(data.compareTo(navigationNode.getData()) < 1){
return false;
}
while(navigationNode != null && navigationNode.getNext() != null && (data.compareTo(navigationNode.getNext().getData()) > 0 || data.compareTo(navigationNode.getData()) == 0)){
navigationNode = navigationNode.getNext();
}
SkipNode<T> searchNodeStart = navigationNode.getDown();
SkipNode<T> searchNodeEnd = navigationNode.getNext().getDown();
while(searchNodeStart != searchNodeEnd){
if(searchNodeStart.getData().compareTo(data) == 0){
return true;
}
searchNodeStart = searchNodeStart.getNext();
}
return false;
}
private static class SkipNode<T>{
public SkipNode(T data){
this.data = data;
}
private SkipNode<T> next = null;
private SkipNode<T> previous = null;
private SkipNode<T> down = null;
private T data;
public SkipNode<T> getNext() {
return next;
}
public void setNext(SkipNode<T> next) {
this.next = next;
}
public SkipNode<T> getPrevious() {
return previous;
}
public void setPrevious(SkipNode<T> previous) {
this.previous = previous;
}
public SkipNode<T> getDown() {
return down;
}
public void setDown(SkipNode<T> down) {
this.down = down;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
}
}
I would like to receive review comments on this code (better ways to search in a SkipList and the adjusting mechanism). I have assumed the user enters the numbers in ascending order. I will apply some sorting mechanism later and post that code too.
