用Java实现通用SkipList

Question

我对实现高级数据结构感兴趣。其中一个让我觉得好笑的是SkipList。

我想知道我的代码中是否有什么需要改进的地方。

SkipList节点：

/**
*   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()); }
}

SkipList高度发生器：

/**
*   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");
    }
    */
}

实际的SkipList类：

/**
*   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());
    }       

}

考试班：

/**
*   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();   
    }
}

Answer 1

    if (levels >= height)
        while (height <= levels)
            buildEmptyLevel();

别担心，while结构在运行之前会检查条件。不需要这里的如果。

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;
}

这是不可维护的。你有死代码，注释解释了显而易见的，没有括号.

你应该删除死密码。

您应该清除那些说了明显的事情的注释，比如“还应该检查是否发现一个节点小于或等于您正在寻找的节点”。用你正在做的事情来代替它们。

您应该添加大括号以澄清代码。

Answer 2

Null检查

使用toString方法检查空不是一个好主意：

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

如果列表与字符串一起使用，而包含"null"内容的字符串是有效值，则会发生什么情况？在这种情况下，您的列表将不能正常工作。

您可以替换该条件以检查数据是否为null。代码将更加清晰和高效，因为它不需要使用String(不需要调用toString和equals )：

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