Skip to content

SkipList ​

SkipList<T> is an ordered set backed by a skip list: a linked list of nodes threaded with randomized express lanes. It keeps every element in sorted order and ignores duplicate inserts. Levels are drawn at random up to 16, so each search, insertion and removal is O(log n) on average, and the lane layout requires no rebalancing. The native handle is released automatically when the binding goes out of scope.

Construction ​

SyntaxDescription
SkipList<T>()Create a new empty skip list

T can be any integer type, any float type, boolean, or string.

Methods ​

MethodSignatureReturnsDescription
insert(T) => booleanbooleanAdd an element; returns true when it was not present
remove(T) => booleanbooleanRemove an element; returns true when it was present
contains(T) => booleanbooleanWhether the element is in the list
min() => T?T?Smallest element, or no value when empty
max() => T?T?Largest element, or no value when empty
len() => usizeusizeNumber of elements
isEmpty() => booleanbooleanWhether the list is empty
clear() => voidvoidRemove all elements

Complexity ​

OperationTime Complexity
insertO(log n) expected
removeO(log n) expected
containsO(log n) expected
minO(1)
maxO(n)
len / isEmptyO(1)
clearO(n)

The expected logarithmic bounds hold for any insertion order, because the express lanes are built from randomized levels rather than from the history of updates; the two lane extremes are found by walking the bottom lane, so min reads the first node and max walks to the last one.

Examples ​

Complete example ​

tyrus
import { SkipList } from "tyrus:algorithm";

const main = (): void => {
    const s = SkipList<i32>();
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(2);

    print(s.len());        // 3 (duplicates are ignored)
    print(s.contains(2));  // true
    print(s.min() ?? 0);   // 1
    print(s.max() ?? 0);   // 3

    s.remove(2);
    print(s.contains(2));  // false
    print(s.isEmpty());    // false

    s.clear();
    print(s.isEmpty());    // true
    print(s.len());        // 0
};

String ordering ​

tyrus
import { SkipList } from "tyrus:algorithm";

const main = (): void => {
    const words = SkipList<string>();
    words.insert("banana");
    words.insert("apple");
    words.insert("cherry");

    print(words.min() ?? "none");  // "apple"
    print(words.max() ?? "none");  // "cherry"
};