@data-structs/skip-list

A generalized self-balancing skip list implemented in Javascript. You can insert any value types you wish so long as you provide your own comparator function. The default comparator is (a, b) => a - b which only allows for numeric comparisons. As you might guess, values are considered equal when the comparator function returns 0.

The algorithm for height-selection is more predictably balanced than a traditional coin-flip model while maintaining an element of randomness in selections. This is accomplished by randomly selecting levels where the expected number of elements is fewer than the actual number of elements in that level. The expected number of elements for a level is calculated using Math.floor((2**(-1 * level)) * n) which ensures each subsequent level has half as many elements as its predecessor, providing O(log n) insertions and searches with high probability.

Installation

yarn add @data-structs/skip-list

Usage

import skipList from '@data-structs/skip-list'

const mySkipList = skipList(
  Array.from(Array(16), () => Math.floor(Math.random() * (16 * 2)))
)

skipList.size        // 16
skipList.insert(196) // 17
skipList.has(196)    // true
skipList.remove(196) // 16
skipList.forEach(console.log)

Implementation details

[3] Sentinel ->                                                948
[2] Sentinel ->                    545 <>                      948
[1] Sentinel ->             302 <> 545 <>               926 <> 948 
[0]            32 <> 218 <> 302 <> 545 <> 840 <> 855 <> 926 <> 948

• All levels are implemented using doubly-linked lists
• O(1) insert at head + tail
  • Ultra-fast inserts when the inserted value is certainly less than or equal to the head or certainly greater than or equal to the tail
• O(log(n)) insert at mid with high probability
• O(1) remove at head + tail
  • Ultra-fast inserts when the removed value is certainly the head or certainly the tail
• O(log(n)) remove at mid with high probability
• O(log(n)) search with high probability
• O(1) search bailout when value is certainly less than the head value or certainly greater than the tail value
• O(n log(n)) space complexity