SkipList package is a free and still
powerful tool to manage large amounts of ordered data, dictionaries, look-up tables etc.
It is based on the well known concept of William Pugh and is highly optimized for Java applications.
- It is very FAST: better than red-black trees or hash tables (but slower than HybridList)
- It is EASY to use: overload compare functions and that's it!
- Search, insert, delete operations require O (lg n) comparisons in most
cases ( all cases in HybridList)
- As every insertion sort it is stable - it retains the original ordering of
- It is in-place algorithm - no additional memory or stack is required
The idea of skip lists is that some nodes are linked not only with its adjacent
neighbors but with nodes that are located much further. See Michel Black's page
for more details.
Test applet that sort 100,000 nodes with random int values:
Short description of SkipList functions:
SkipList(); //default constructor
int getNumber(); // returns number of nodes in the list
boolean Insert (SkipListNode node); //inserts node in the list
boolean Remove (SkipListNode node); //removes nodes from the list
void RemoveAll (); //removes all nodes from the list
SkipListNode RemoveHead (); //removes first node
SkipListNode Find (SkipListNode node); //returns first node which is equal to the sample
SkipListNode FindSimilar (SkipListNode node);//returns first node which is similar to the sample
SkipListNode Find (long long_val); //searches node by long value
SkipListNode FindSimilar (long long_val); //searches node by long value
SkipListNode Find (double double_val); //searches node by double value
SkipListNode FindSimilar (double double_val);//searches node by double value
SkipListNode Find (String string_val,boolean ignore_case); //searches node by String value
SkipListNode FindSimilar (String string_val,boolean ignore_case);//searches node by String value
SkipListNode getHead (); //returns first node of the list
SkipListNode getNext (SkipListNode node); //returns next node
SkipListNode getPrev (SkipListNode node); //returns previous node (works only with double-linked nodes)
Fully functional version of SkipList is free and available for
download. Registered users of HybridList
package also get the source code of SkipList.
to JAVIR homepage