canonical skiplist insertion

skiplistinsert.java

import java.util.Random;

public class SkipList {
    private static final int MAX_LEVEL = 7;
    private Random rng;
    private class Node {
        public Character info;
        public int level;
        public Node[] forward;
        Node(char i, int level) {
            this.info = i;
            this.level = level;
            this.forward = (Node[]) new Node[level];
        }
    }
    int height;
    private Node head;
    public SkipList(Character minVal) {
        head = new Node(minVal, MAX_LEVEL);
        height = 0;
        rng = new Random();
    }
    int pickHeight() {
        int i = 1;
        while (rng.nextInt(100) < 50) i++;
        if (i > MAX_LEVEL) i = MAX_LEVEL;
        return i;
    }
    public void insert(Character info) {
        Node[] stack = (Node[]) new Node[MAX_LEVEL];
        Node u = head;
        int comp = 0;
        int i = height;
        while (i >= 0) {
            while (u.forward[i] != null && (comp = u.forward[i].info.compareTo(info)) < 0) 
                u = u.forward[i];
            stack[i--] = u;
        }
        Node w = new Node(info, pickHeight());
        while (height < w.level) 
            stack[++height] = head;
        for (i = 0; i < w.forward.length; i++) {
            w.forward[i] = stack[i].forward[i];
            stack[i].forward[i] = w;
        }
    }

    public void show() {
        for (int i = height-1; i >= 0; i--) {
            for (Node t = head; t != null; t = t.forward[i]) {
                System.out.print(t.info + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        String s = "ASKIPLISTEXAMPLE";
        SkipList sl = new SkipList('A');
        for (int i = 0; i < s.length(); i++) {
            sl.insert(s.charAt(i));
        }
        sl.show();
    }
}