4
\$\begingroup\$

I am interested in implementing advanced data structures. One of them that tickled my fancy is the SkipList.

I wanted to know if there is anything to improve in my code.

The SkipList node:

/**
*   SKNode.java
*/

import java.io.Serializable;

class SKNode<T extends Comparable<? super T>> implements Serializable{
    private SKNode<T> up = null;
    private SKNode<T> down = null;
    private SKNode<T> next = null;
    private SKNode<T> prev = null;
    private int printPosition = 0;
    private T data;

    SKNode(T data){ this.data = data;}

    public void setUp(SKNode<T> up){this.up = up;}
    public void setDown(SKNode<T> down){this.down = down;}
    public void setNext(SKNode<T> next){this.next = next;}
    public void setPrev(SKNode<T> prev){this.prev = prev;}
    public void setPrintPosition(int printPosition){ this.printPosition = printPosition;}

    public T getData(){return data;}        
    public SKNode<T> getUp(){return up;}
    public SKNode<T> getDown(){return down;}
    public SKNode<T> getNext(){return next;}
    public SKNode<T> getPrev(){return prev;}
    public int getPrintPosition(){ return printPosition;}

    @Override
    // To avoid NullPointerException, we check if object is null, if it is, print "null" 
    public String toString(){ return (data == null ? "null" : data.toString()); }
}

The SkipList height generator:

/**
*   File: SkipHeightGen.java
*/
import java.util.Random;
import java.util.ArrayList;

public class SkipHeightGen{

    private Random rand;
    private int maxLevel;
    // Ideally the probability should be somewhere between
    // 1/2, 1/3, 1/e
    private double probability;
    // For the different implementations of the 
    // SkipList, the initialLevel can either be 0(quad-node pointers) 
    // or 1(array version)
    private int initLevel;

    public SkipHeightGen(int initLevel, int maxLevel){
        this(initLevel, maxLevel, 0.0);
    }

    public SkipHeightGen(int initLevel, 
            int maxLevel, double probability){
        this.initLevel = initLevel;
        this.maxLevel = maxLevel;
        this.probability = probability;
        rand = new Random();
    }

    public int manLevel(){

        int row = initLevel;

        // Return a number between 1 and the maxLevel
        // with a certain probability
        while((rand.nextFloat() < probability) &&
            (row  < maxLevel))
            row++;

        return row;
    }

    // More even distribution
    public int simpleLevel(){

        int row = initLevel;

        // Return a certain randow level
        while( rand.nextBoolean())
            row++;

        if (row >= maxLevel)
            row--;
        return row;
    }

    /**
    public static void main(String[] args){
        SkipHeightGen n = new SkipHeightGen(1, 16, 0.5);
        SkipHeightGen nl = new SkipHeightGen(1);

        ArrayList al  = new ArrayList();
        ArrayList l = new ArrayList();

        for (int i = 0; i < 14; i++){
            al.add(n.manLevel());
            l.add(nl.simpleLevel());
        }

        System.out.print("manLevel: " + al + 
            "\nsimpleLevel: " + l + "\n");
    }
    */
}

The actual SkipList class:

/**
*   File: SkipLinkedList.java
*/

import java.io.Serializable;

public class SkipLinkedList<T extends Comparable<T>> implements Serializable{

    private SKNode<T> head;
    private SKNode<T> tail;

    private SkipHeightGen rand;
    private int height;
    private int nodeCount;

    SkipLinkedList(){
        nodeCount = 0; 
        height = 0;
        rand = new SkipHeightGen(0, 16);    // maxLevel = 16;

        SKNode<T> negInf = new SKNode<>(null);
        SKNode<T> posInf = new SKNode<>(null);

        negInf.setNext(posInf);
        posInf.setPrev(negInf);

        head = negInf;
        tail = posInf;
    }

    public boolean isEmpty(){ return nodeCount == 0;}

    public int size(){ return nodeCount;}

    public int getHeight() { return height;}

    private SKNode<T> find(T data){
        SKNode<T> curPos = head;
        // while(curPos != null) -- Possible alteration
        /**
        while(!curPos.toString().equals("null") 
            && curPos.getData().compareTo(data) != 0){
            if (curPos.getNext().getData().compareTo(data) > 0)
                curPos = curPos.getDown();
            else
                curPos = curPos.getNext();
            if (curPos == null) break;
        }*/
        while (true){
            // Check to see you have not reached the end of the row
            // and also check to see if you have not found a node either
            // less than or equal to what you are looking for.
            while(!(curPos.getNext().toString().equals("null")) &&
                curPos.getNext().getData().compareTo(data) <= 0)
                curPos = curPos.getNext();
            // If node is found, move down a level below
            if (curPos.getDown() != null)
                curPos = curPos.getDown();
            else
            // On the last level, stop
                break;      
        }
        return curPos;
    }

    public boolean insert(T data){
        if (data == null) throw new IllegalArgumentException("Data cannot be null");
        SKNode<T> curPos = find(data);
        System.out.println("Predecessor: " + curPos.toString());
        if (!curPos.toString().equals("null") &&
            curPos.getData().compareTo(data) == 0)
            return false;
        SKNode<T> toInsert = new SKNode<T>(data);
        toInsert.setNext(curPos.getNext());
        toInsert.setPrev(curPos);
        curPos.getNext().setPrev(toInsert);
        curPos.setNext(toInsert);
        System.out.println("Inserted " + data + "on lowest level") ;
        int levels = rand.simpleLevel(); 
        System.out.println("Constructing : " + levels + " levels");
        if (levels > 0)
            buildTowers(toInsert, curPos, levels);
        nodeCount++;
        return true;
    }

    private void buildTowers(SKNode<T> curPos, SKNode<T> prevPos, int levels){
        int initHeight = height;
        int offset;
        if (levels >= height)
            while (height <= levels)
                buildEmptyLevel();

        if (levels < height) 
            initHeight = 0;
        if (levels > initHeight)    
            offset = levels - initHeight;
        else
            offset = 1;
        for (int counter = 0; counter < offset; counter++){
            while(prevPos.getUp() == null)
                prevPos = prevPos.getPrev();
            prevPos =  prevPos.getUp();

            System.out.println("Inserting " +  curPos.getData().toString() 
                        + " for Round :" + counter);
            SKNode<T> towerNode = new SKNode<T> (curPos.getData());
            towerNode.setPrev(prevPos);
            towerNode.setNext(prevPos.getNext());
            prevPos.getNext().setPrev(towerNode);
            prevPos.setNext(towerNode);
            towerNode.setDown(curPos);
            curPos.setUp(towerNode);
            curPos = towerNode;
        }       
    }

    private void buildEmptyLevel() {
        SKNode<T> tempHead = new SKNode<T>(null);
        SKNode<T> tempTail = new SKNode<T>(null);
        tempHead.setNext(tempTail);
        tempTail.setPrev(tempHead);
        tempHead.setDown(head);
        tempTail.setDown(tail);
        head.setUp(tempHead);
        tail.setUp(tempTail);
        head = tempHead;
        tail = tempTail;
        System.out.println("\nBuilt empty level!!");
        height++;
    }

    public boolean contains(T data){
        if (data.compareTo(find(data).getData()) == 0)
            return true;
        return false;
    }   

    public boolean remove(T data){
        if (!contains(data))
            return false;
        SKNode<T> curPos = find(data);
        SKNode<T> prevPos = curPos.getPrev();
        while(true){
            prevPos.setNext(curPos.getNext());
            curPos.getNext().setPrev(prevPos);
            curPos.setNext(null);
            curPos.setPrev(null);
            curPos.setUp(null);
            curPos = null;
            while(prevPos.getUp() == null)
                prevPos = prevPos.getPrev();
            prevPos = prevPos.getUp();
            if (prevPos == head && prevPos.getNext() == tail)
                break;
            curPos = prevPos.getNext();
            curPos.setDown(null);   
        }
        nodeCount--;
        if ((head.getDown().getNext() == tail.getDown()))
            removeEmptyLevel();
        return true;
    }

    private void removeEmptyLevel(){
        SKNode<T> tempHead = head;
        SKNode<T> tempTail = tail;
        head = head.getDown();
        tail = tail.getDown();
        head.setUp(null);
        tail.setUp(null);
        tempHead.setDown(null);
        tempTail.setDown(null);
        tempHead.setNext(null);
        tempTail.setPrev(null);
        tempHead = null;
        tempTail = null;
    }


    /**
    * Display methods
    */
    @Override
    public String toString(){
        return printHorizontally().toString();
    }

    private StringBuilder printHorizontally(){
        StringBuilder sb = new StringBuilder();
        SKNode<T> curPos = head;
        while (curPos.getDown() != null)
            curPos = curPos.getDown();

        while ( curPos != null){
            SKNode<T> pos = curPos;
            sb.append(getColumn(pos));
            sb.append("\n");
            curPos = curPos.getNext();          
        }
        return sb;
    }

    private String getColumn(SKNode<T> pos){
        String row = " ";
        while(pos != null){
            row = row + pos.toString() + " ";
            pos = pos.getUp();
        }
        return row;
    }

    public void printVertically(){
        SKNode<T> curPos = head;
        while(curPos.getDown() != null)
            curPos = curPos.getDown();
        int i = 0;
        while (curPos != null){
            curPos.setPrintPosition(i++);
            curPos = curPos.getNext();
        }
        curPos = head;
        while(curPos != null){
            printOneRow(curPos);
            curPos = curPos.getDown();
        }
    }

    private void printOneRow(SKNode<T> curPos){
        StringBuilder sb = new StringBuilder();
        SKNode<T> walk =  curPos;
        sb.append(walk.toString());
        walk = walk.getNext();
        int n = 0, counter;

        while(walk != null){
            SKNode<T> n_walk = walk;
            while(n_walk.getDown() != null)
                n_walk = n_walk.getDown();
            int max_pos = n_walk.getPrintPosition();

            sb.append("<=");            
            for (counter = n + 1; counter < max_pos; counter++)
                sb.append("====");
            sb.append(">" + walk.toString());
            counter = max_pos;
            walk = walk.getNext();
        }
        System.out.println(sb.toString());
    }       

}

The test class:

/**
*   File: SkipLinkedListTest.java
*/

public class SkipLinkedListTest{

    public static void main (String[] args){
        SkipLinkedList<Integer> sk = new SkipLinkedList<>();
        System.out.println("Is it empty? : " + sk.isEmpty());
        System.out.println(sk);
        sk.insert(30);
        System.out.println("How many? : " + sk.size());
        System.out.println(sk);
        sk.insert(5);
        System.out.println("How many? : " + sk.size());
        System.out.println(sk);
        sk.insert(6);
        System.out.println("How many? : " + sk.size());
        System.out.println(sk);
        sk.insert(7);
        System.out.println("How many? : " + sk.size());
        System.out.println(sk);
        sk.insert(50);
        System.out.println("How many? : " + sk.size());
        System.out.println(sk);
        sk.printVertically();
        sk.remove(7);
        System.out.println("How many? : " + sk.size());
        System.out.println(sk);
        sk.printVertically();   
    }
}
\$\endgroup\$
1
  • 4
    \$\begingroup\$ HI. Welcome to Code Review! It's often helpful if you explain what a Skip List does and possibly link to additional explanation. At minimum, you should explain when you would use it. Possibly example input and output. \$\endgroup\$
    – mdfst13
    Jul 5, 2016 at 11:31

2 Answers 2

3
\$\begingroup\$
    if (levels >= height)
        while (height <= levels)
            buildEmptyLevel();

Don't worry, a while construct will check the condition before running. No need for the if here.


private SKNode<T> find(T data){
    SKNode<T> curPos = head;
    // while(curPos != null) -- Possible alteration
    /**
    while(!curPos.toString().equals("null") 
        && curPos.getData().compareTo(data) != 0){
        if (curPos.getNext().getData().compareTo(data) > 0)
            curPos = curPos.getDown();
        else
            curPos = curPos.getNext();
        if (curPos == null) break;
    }*/
    while (true){
        // Check to see you have not reached the end of the row
        // and also check to see if you have not found a node either
        // less than or equal to what you are looking for.
        while(!(curPos.getNext().toString().equals("null")) &&
            curPos.getNext().getData().compareTo(data) <= 0)
            curPos = curPos.getNext();
        // If node is found, move down a level below
        if (curPos.getDown() != null)
            curPos = curPos.getDown();
        else
        // On the last level, stop
            break;      
    }
    return curPos;
}

This is unmaintainable. You've got dead code, comments explaining the obvious, lack of brackets...

You should remove the dead code.

You should clear away the comments that say obvious things like "and also check to see if you have not found a node either less than or equal to what you are looking for". Replace them with why you are doing what you are doing.

You should add braces to clarify the code.

\$\endgroup\$
2
\$\begingroup\$

Null checks

Use the toString method to check for nulls is not a good idea:

public String toString(){ return (data == null ? "null" : data.toString()); }
...   
while(!(curPos.getNext().toString().equals("null")) &&
      curPos.getNext().getData().compareTo(data) <= 0)

What happens if the List is being used with strings and the string with a content of "null" is a valid value? In that case your list won't work correctly.

You can replace the condition to check if the data is null. The code would be a little more clear and more efficient as it doesn't need to work with Strings (The calls to toString and equals are not needed):

while(curPos.getNext().getData() != null &&
      curPos.getNext().getData().compareTo(data) <= 0)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.