This is C89 implementation of the data type described in William Pugh's paper with widths.
Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
Using widths allows for efficient random access.
Although this library will work with C and C++, if you perfer fancy C++ objects you can check out my first implementation of skip lists
Skip Lists allow insertion, deletion, random access and search in O(log n) on average (and O(n) in worst case). Skip lists are a simple data structure that can be used in place of balanced trees for most applications and are much less daunting.
This library is written in standard C89 for portability.
The idea behind single-header file libraries is that they're easy to distribute and deploy because all the code is contained in a single file. The .h file acts as its own header files, i.e. it declares the functions and classes contained in the file but no code is getting compiled.
So in addition, you should select exactly one C/C++ source file that actually instantiates the code, preferably a file you're not editing frequently.
This file should define JRSL_IMPLEMENTATION to actually enable the function definitions.
You can check out example.c for some sample code.
| Function | Effect |
|---|---|
| Creation and deletion | |
| jrsl_initialize() | Initializes a skip list |
| jrsl_destroy() | Cleans up a skip list |
| Size and capacity | |
| jrsl_max_level() | Calculates the optimal maximum for the amount of levels |
| Element access | |
| jrsl_data_at() | Returns the data at a particular index |
| jrsl_key_at() | Returns the key at a particular index |
| Modification | |
| jrsl_insert() | Inserts an element (a key and some data) in the skip list and returns `NULL` |
| jrsl_remove() | Removes an element from the skip list, deletes the key and returns it's data |
| Searching | |
| jrsl_search() | Returns the data of the node with a given key |
| Visualization | |
| jrsl_display_list() | Prints a visual representation of the skip list |
All contributions are welcome!
This library is in the public domain. You can do anything you want with it. You have no legal obligation to do anything else, although I appreciate attribution.
It is also licensed under the MIT open source license, if you have lawyers who are unhappy with public domain. The source file includes an explicit dual-license for you to choose from.