手写跳跃表java,SkipList跳跃表（Java实现）

取自网络https://github.com/spratt/SkipList

AbstractSortedSet.java

package skiplist_m;

/******************************************************************************

* AbstractSortedSet *

* *

* Extends AbstractSet and implements SortedSet, and contains stub methods *

* *

* View README file for information about this project. *

* View LICENSE file for license information. *

******************************************************************************/

import java.util.*;

abstract class AbstractSortedSet

extends AbstractSet

implements SortedSet {

public E first() {

return null;

}

public E last() {

return null;

}

public Iterator iterator() {

return null;

}

public SortedSet headSet(E toElement) {

return null;

}

public SortedSet tailSet(E fromElement) {

return null;

}

public SortedSet subSet(E fromElement, E toElement) {

return null;

}

public Comparator super E> comparator() {

return null; // uses natural ordering

}

}

SkipList.java

package skiplist_m;

/******************************************************************************

* Skiplist *

* *

* View README file for information about this project. *

* View LICENSE file for license information. *

******************************************************************************/

import java.util.Iterator;

public class SkipList> extends AbstractSortedSet {

private SkipListNode head;

private int maxLevel;

private int size;

private static final double PROBABILITY &＃61; 0.5;

public SkipList() {

size &＃61; 0;

maxLevel &＃61; 0;

// a SkipListNode with value null marks the beginning

head &＃61; new SkipListNode(null);

// null marks the end

head.nextNodes.add(null);

}

public SkipListNode getHead() {

return head;

}

// Adds e to the skiplist.

// Returns false if already in skiplist, true otherwise.

public boolean add(E e) {

if(contains(e)) return false;

size&＃43;&＃43;;

// random number from 0 to maxLevel&＃43;1 (inclusive)

int level &＃61; 0;

while (Math.random()

level&＃43;&＃43;;

while(level > maxLevel) { // should only happen once

head.nextNodes.add(null);

maxLevel&＃43;&＃43;;

}

SkipListNode newNode &＃61; new SkipListNode(e);

SkipListNode current &＃61; head;

do {

current &＃61; findNext(e,current,level);

newNode.nextNodes.add(0,current.nextNodes.get(level));

current.nextNodes.set(level,newNode);

} while (level-- > 0);

return true;

}

// Returns the skiplist node with greatest value <&＃61; e

private SkipListNode find(E e) {

return find(e,head,maxLevel);

}

// Returns the skiplist node with greatest value <&＃61; e

// Starts at node start and level

private SkipListNode find(E e, SkipListNode current, int level) {

do {

current &＃61; findNext(e,current,level);

} while(level-- > 0);

return current;

}

// Returns the node at a given level with highest value less than e

private SkipListNode findNext(E e, SkipListNode current, int level) {

SkipListNode next &＃61; (SkipListNode)current.nextNodes.get(level);

while(next !&＃61; null) {

E value &＃61; (E)next.getValue();

if(lessThan(e,value)) // e

break;

current &＃61; next;

next &＃61; (SkipListNode)current.nextNodes.get(level);

}

return current;

}

public int size() {

return size;

}

public boolean contains(Object o) {

E e &＃61; (E)o;

SkipListNode node &＃61; find(e);

return node !&＃61; null &&

node.getValue() !&＃61; null &&

equalTo((E)node.getValue(),e);

}

public Iterator iterator() {

return new SkipListIterator(this);

}

/******************************************************************************

* Utility Functions *

******************************************************************************/

private boolean lessThan(E a, E b) {

return a.compareTo(b) <0;

}

private boolean equalTo(E a, E b) {

return a.compareTo(b) &＃61;&＃61; 0;

}

private boolean greaterThan(E a, E b) {

return a.compareTo(b) > 0;

}

/******************************************************************************

* Testing *

******************************************************************************/

public static void main(String[] args) {

SkipList testList &＃61; new SkipList();

System.out.println(testList);

testList.add(4);

System.out.println(testList);

testList.add(1);

System.out.println(testList);

testList.add(2);

System.out.println(testList);

testList &＃61; new SkipList();

System.out.println(testList);

testList.add("hello");

System.out.println(testList);

testList.add("beautiful");

System.out.println(testList);

testList.add("world");

System.out.println(testList);

}

public String toString() {

String s &＃61; "SkipList: ";

for(Object o : this)

s &＃43;&＃61; o &＃43; ", ";

return s.substring(0,s.length()-2);

}

}

SkipListIterator.java

package skiplist_m;

/******************************************************************************

* SkipListIterator *

* *

* View README file for information about this project. *

* View LICENSE file for license information. *

******************************************************************************/

import java.util.*;

public class SkipListIterator> implements Iterator {

SkipList list;

SkipListNode current;

public SkipListIterator(SkipList list) {

this.list &＃61; list;

this.current &＃61; list.getHead();

}

public boolean hasNext() {

return current.nextNodes.get(0) !&＃61; null;

}

public E next() {

current &＃61; (SkipListNode)current.nextNodes.get(0);

return (E)current.getValue();

}

public void remove() throws UnsupportedOperationException {

throw new UnsupportedOperationException();

}

}

SkipListNode.java

package skiplist_m;

/******************************************************************************

* SkipListNode *

* *

* View README file for information about this project. *

* View LICENSE file for license information. *

******************************************************************************/

import java.util.*;

public class SkipListNode {

private E value;

public List > nextNodes;

public E getValue() {

return value;

}

public SkipListNode(E value) {

this.value &＃61; value;

nextNodes &＃61; new ArrayList >();

}

public int level() {

return nextNodes.size()-1;

}

public String toString() {

return "SLN: " &＃43; value;

}

}