/** FILE: SkipList.java AUTHOR: Cheng, Jeff LAST CHANGE: 3-22-02 PURPOSE: An alternative to linked list. Extremely fast, for reasons similar to having pointers at every 2^ith node, and randomization. FUCNTIONS: SkipList(size)-------------> creates a empty skip list, essentially a linked list of size 2, with each node. growing to the maximum height; first node == -1 and second node == maximum value + 1. createAndSearch(size, x)---> creates a skip list of given size and search for x randomly chosen nodes, and time each operations and display on the screen. insertAfterAbove(p, q, i)--> insert a node after p and above q with value == i, and returns a reference to this node. printList()----------------> prints out the entire list. randomLevels()-------------> randomize the height of each node to be inserted. searchList(key)---------------> searches the skip list for a node containig the key sought, returns a reference to the node. The calling function should check to see if searchList returns a reference to the node being sought or the node before it, because the value may not be in the skip list. showRelationships()--------> prints out the nodes around this node if there exists one, otherwise prints out a warning message. skipInsert(value)---------------> inserts a node with value x in the skip list: there will be one new node at s0, a linked list, and this new node will grow to a random height upon insertion. CREDIT: Adapted from Professor Ed Lank's lecture, SFSU. COPYRIGHT: You may use, modify, or distribute my code for non-commerical use only; you must cite me, Jeff Cheng, as the source. */ package lists; public class SkipList{ private static Nodes head; // upper left-hand node, value = -infinity, e.g. -1. private static Nodes topLeft; /* maximum levels/height in the skiplist. Note: levels will always be >= 3, because levels = 1 + max(log2(listSize), 1) for ease of computation. This is a waste with small number of nodes, but as the number of nodes increases, the effects become minimal.*/ int MAX_LEVEL; /* builds a 2*MAX_LEVEL SkipList, where nodes in the first column = -1, and nodes in the second column = MAX_VALUE + 1 */ public SkipList(int listSize){ // maximum levels = 2 * log2 listSize, guaranteed to be at least 2 MAX_LEVEL = 2 * Math.max((int)(Math.log((double)listSize)/Math.log((double)2)), 1); // maximum value is 5 * listSize int MAX_VALUE = 5 * listSize; /* "points" to the first node in linked list at s0 first node's value = -infinity; we use -1 */ head = new Nodes(-1); // now let p "points" to this first node Nodes p = head; // set up the last, rightmost node at s0, value = +infinity p.setNext(new Nodes(MAX_VALUE + 1)); // now let q "points" to this last node Nodes q = p.getNext(); q.setPrevious(p); // now setup the remaining nodes in the two "vertical" linked lists for (int i = 0; i < MAX_LEVEL; i++){ // now proceed to create a node with value = -infinity p.insertAbove(-1); // now move up one node; 1 row that is. p = p.getAbove(); // now proceed to create a node with value = +infinity q.insertAbove(MAX_VALUE + 1); // now move up one node, 1 row that is. q = q.getAbove(); /* finally, fix the "pointers," so nodes "pointed by" p and q now will "point" to each other */ p.setNext(q); q.setPrevious(p); } /* topLeft is the node always containing a -1 value, or negative infinity */ topLeft = p; } // randomize the height of the skip list public int randomLevels(){ int height = 1; while(Math.random() < 0.5){ /* let's flip a coin; the fewer times we flip a tail, e.g. Math.random < 0.5, the smaller the height, and thus the fewer levels.*/ height++;} // height <= MaxLevels return Math.min(height, MAX_LEVEL);} // search for a node containing the specified key public Nodes searchList(int key){ Nodes p = topLeft; /* as long as we are not at linked list at s0 we may advance forward if the next node in line, (this is, horizontally) contains a value <= key being sought e.g. while nextNode.value <= key, getNextNode so we go forward if next node <= key, else we go downward and repeat the process, until we get to the bottom level. Note searchList does not tell us if the key being sought exists in the list or not.*/ while (p.getBelow()!=null){ while (p.getNext().getValue() <= key){ p = p.getNext();} p = p.getBelow();} /* we are now at the bottom level, at s0 let's see if the key we want is between values contained in nodes at level s0, e.g. searching for a 5 after 3 and 4 on level s0, where 3, 4, and 5 are nodes of height 0. e.g. only one node with nothing above them*/ while (p.getNext().getValue() <= key){ p = p.getNext();} return p;} /* insert a node after p and above q, and return a reference to the inserted node to the calling function/variable*/ public Nodes insertAfterAbove(Nodes p, Nodes q, int value){ // node to be inserted Nodes node = new Nodes(value); /* fix "pointers" so that p <-> node ^ | q */ // horizontal links node.setNext(p.getNext()); node.getNext().setPrevious(node); node.setPrevious(p); p.setNext(node); // vertical links node.setBelow(q); /* if not inserting above null, then link the node right under this node as well */ if (q != null){q.setAbove(node);} return node;} /* insert a node in the skip list, and builds a linked list above this node of random height Calls searchList(int key) and insertAfterAbove(Nodes p, Nodes q, int value)*/ public void skipInsert(int value){ /* after searchList, we've found the node right before where we wish to insert a node with value given. Let p "points" to this node*/ Nodes p = searchList(value); /* insert between this node, now p, and before the next node, and therefore, above null*/ Nodes q = insertAfterAbove(p, null, value); // randomize the levels to go up on this node int level = randomLevels(); for (int i = 1; i < level; i++){ /* if there is not at least one node above the current node where p is, then the new node just created (at q) will need to find another node on the next higher level to add a node above it. So move forward, e.g. p = p.previous and try going up again, and repeat the process until we found a node at the same level at which the "to be" node pointed by q.above is. e.g. x <-- found it! (q.above) y y y y y y y y y y y y q */ while (p.getAbove() == null){ p = p.getPrevious();} p = p.getAbove(); q = insertAfterAbove(p, q, value);} } /* create and search builds a skip list of specified listSize, and search for x randomly chosen nodes, and displays the time needed to do the work Note: nodes can only contain values between 0 and 1/100 the listSize e.g.if listSize = 1000 0 <= value <= 10 */ public static void createAndSearch(int listSize, int x){ boolean DEBUG = false; // to keep track of time needed to do something // maximum value allowed is 5 * listSize int MAX_VALUE = 5 * listSize; long timeBegan = 0; long timeFinished = 0; long timeNeeded = 0; // create a skip list of a specified listSize timeBegan = System.currentTimeMillis(); // an empty skiplist, e.g. Actually has two nodes // of height MAX_LEVEL, but contain invalid values SkipList aSkipList = new SkipList(listSize); // now create the skiplist we really want, // with 2+listSize nodes at s0, which is really just // a linked list. for (int i = 0; i < listSize; i++){ aSkipList.skipInsert((int)(Math.random()*MAX_VALUE));} timeFinished = System.currentTimeMillis(); timeNeeded = timeFinished - timeBegan; System.out.println("\n\t Time needed to generate a skip list "+ "of listSize " + listSize + " = " + timeNeeded + " milliseconds."); // search for x randomly chosen nodes timeBegan = System.currentTimeMillis(); for (int i = 0; i < x; i++){ aSkipList.searchList((int)(Math.random()*MAX_VALUE));} timeFinished = System.currentTimeMillis(); timeNeeded = timeFinished - timeBegan; System.out.println("\t Searching for " + x + " randomly chosen nodes " + "took = " + timeNeeded + " milliseconds."); if(DEBUG){ aSkipList.printList(); aSkipList.showRelationships(); } } /* utility functions to print out values not needed to display output in class lists Quite different from class LinkedList, so decided not to extend from class LinkedList walks through the entire list, and prints out the values contained in each node */ public void printList(){ /* if the list is empty, we are done.*/ if (head == null){return;} /* otherwise, print the values one-by-one until we reach the end of the list. e.g. null*/ for (Nodes n = head; n != null; n = n.getNext()){ for (Nodes m = n; m != null; m = m.getAbove()){ System.out.println(m.getValue());} } } /* showRelationships() goes through the entire linked list, and prints out for each node, the node before, after, above, and below it, if not null. If it is null, prints out a warning message.*/ public void showRelationships(){ for (Nodes n = head; n != null; n = n.getNext()){ for (Nodes m = n; m != null; m = m.getAbove()){ // get previous node if (m.getPrevious() != null){ System.out.println("Previous: "+m.getPrevious().getValue());} else if (m.getPrevious() == null){ System.out.println("Previous: null; logic error.");} // get next node if (m.getNext() != null){ System.out.println("Next: "+m.getNext().getValue());} else if (m.getNext() == null){ System.out.println("Next: null; logic error.");} // get above node if (m.getAbove() != null){ System.out.println("Above: "+m.getAbove().getValue());} else if (m.getAbove() == null){ System.out.println("Above: null; logic error.");} // get below node if (m.getBelow() != null){ System.out.println("Below: "+m.getBelow().getValue());} else if (m.getBelow() == null){ System.out.println("Below: null; logic error.");} } } } }