__SkipList package__

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.

__Main features:__

- 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
identical keys
- It is
**in-place** algorithm - no additional memory or stack is required

__Concept:__

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.

__Examples:__

**SkipList_PerformanceTest** -
Test applet that **sort 100,000 nodes** with random int values:

__Short description of SkipList functions:__

**class SkipList **
**//constructors:**
SkipList(); //default constructor
** //info functions:**
int getNumber(); // returns number of nodes in the list
**//insert, remove:**
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
**//find functions:**
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
**//find long:**
SkipListNode Find (long long_val); //searches node by long value
SkipListNode FindSimilar (long long_val); //searches node by long value
**//find double:
**SkipListNode Find (double double_val); //searches node by double value
SkipListNode FindSimilar (double double_val);//searches node by double value
**//find string:
**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
**//navigation:**
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)

__Download:__

Fully functional version of SkipList is **free** and available for
download. Registered users of **HybridList**
package also get the **source code of SkipList**.

Download:
**(30K)**

<- Back
to JAVIR homepage