dataStructures
Class SkipList
java.lang.Object
|
+--dataStructures.SkipList
- public class SkipList
- extends java.lang.Object
- implements Dictionary
Constructor Summary |
SkipList(java.lang.Comparable largeKey,
int maxElements,
float theProb)
create an empty skip list |
Method Summary |
java.lang.Object |
get(java.lang.Object theKey)
|
boolean |
isEmpty()
|
java.util.Iterator |
iterator()
create and return an iterator |
static void |
main(java.lang.String[] args)
test program |
java.lang.Object |
put(java.lang.Object theKey,
java.lang.Object theElement)
insert an element with the specified key
overwrite old element if there is already an
element with the given key |
java.lang.Object |
remove(java.lang.Object theKey)
|
int |
size()
|
java.lang.String |
toString()
convert to a string |
Methods inherited from class java.lang.Object |
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
wait,
wait,
wait |
prob
protected float prob
maxLevel
protected int maxLevel
levels
protected int levels
size
protected int size
tailKey
protected java.lang.Comparable tailKey
headNode
protected SkipList.SkipNode headNode
tailNode
protected SkipList.SkipNode tailNode
last
protected SkipList.SkipNode[] last
r
protected java.util.Random r
SkipList
public SkipList(java.lang.Comparable largeKey,
int maxElements,
float theProb)
- create an empty skip list
- Parameters:
largekey
- used as key in tail node
all elements must have a smaller key than thismaxElements
- largest number of elements
to be stored in the dictionarytheProb
- probability that element on one
level is also on the next level
isEmpty
public boolean isEmpty()
- Returns:
- true iff the skip list is empty
size
public int size()
- Returns:
- current number of elements in the skip list
get
public java.lang.Object get(java.lang.Object theKey)
- Specified by:
- get in interface Dictionary
- Returns:
- element with specified key
put
public java.lang.Object put(java.lang.Object theKey,
java.lang.Object theElement)
- insert an element with the specified key
overwrite old element if there is already an
element with the given key
- Specified by:
- put in interface Dictionary
- Returns:
- old element (if any) with key theKey
- Throws:
- java.lang.IllegalArgumentException - when
theKey >= largeKey = tailKey
remove
public java.lang.Object remove(java.lang.Object theKey)
- Specified by:
- remove in interface Dictionary
- Returns:
- matching element and remove it
toString
public java.lang.String toString()
- convert to a string
- Overrides:
- toString in class java.lang.Object
iterator
public java.util.Iterator iterator()
- create and return an iterator
main
public static void main(java.lang.String[] args)
- test program