JAVIR - SkipList

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.

SkipList.gif (4769 bytes)

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