Skip to main content

SkipList

data-structure-typed

data-structure-typed / SkipList

Class: SkipList<K, V, R>

Defined in: data-structures/linked-list/skip-linked-list.ts:46

SkipList — a probabilistic sorted key-value container.

API mirrors TreeMap: users can swap TreeMap ↔ SkipList with zero code changes. Reference: Java ConcurrentSkipListMap (NavigableMap interface).

Example​

// Display skip list
 const sl = new SkipList<number, string>([[1, 'a']]);
    expect(() => sl.print()).not.toThrow();

Extends​

Type Parameters​

K​

K = any

V​

V = any

R​

R = [K, V]

Accessors​

size​

Get Signature​

get size(): number;

Defined in: data-structures/linked-list/skip-linked-list.ts:79

Total number of entries.

Remarks​

Time O(1), Space O(1)

Returns​

number

Entry count.

Overrides​

IterableEntryBase.size

Methods​

[iterator]()​

iterator: IterableIterator<[K, V | undefined]>;

Defined in: data-structures/base/iterable-entry-base.ts:22

Default iterator yielding [key, value] entries.

Parameters​

args​

...unknown[]

Returns​

IterableIterator<[K, V | undefined]>

Iterator of [K, V].

Remarks​

Time O(n) to iterate, Space O(1)

Inherited from​

IterableEntryBase.[iterator]

ceiling()​

ceiling(key): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:385

Least entry ≥ key, or undefined.

Parameters​

key​

K

Returns​

[K, V | undefined] | undefined

Example​

// Least entry ≥ key
 const sl = new SkipList<number, string>([
      [10, 'a'],
      [20, 'b'],
      [30, 'c']
    ]);
    console.log(sl.ceiling(15)); // [20, 'b'];
    console.log(sl.ceiling(20)); // [20, 'b'];

clear()​

clear(): void;

Defined in: data-structures/linked-list/skip-linked-list.ts:146

Remove all entries

Returns​

void

Example​

// Remove all entries
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [2, 'b']
    ]);
    sl.clear();
    console.log(sl.isEmpty()); // true;

Overrides​

IterableEntryBase.clear

clone()​

clone(): this;

Defined in: data-structures/linked-list/skip-linked-list.ts:164

Create independent copy

Returns​

this

Example​

// Create independent copy
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [2, 'b']
    ]);
    const copy = sl.clone();
    copy.delete(1);
    console.log(sl.has(1)); // true;

Overrides​

IterableEntryBase.clone

delete()​

delete(key): boolean;

Defined in: data-structures/linked-list/skip-linked-list.ts:280

Delete a key. Returns true if the key was found and removed.

Parameters​

key​

K

Returns​

boolean

Example​

// Fast lookup with deletion
 const cache = new SkipList<string, number>();

    cache.set('alpha', 1);
    cache.set('beta', 2);
    cache.set('gamma', 3);

    console.log(cache.has('beta')); // true;
    cache.delete('beta');
    console.log(cache.has('beta')); // false;
    console.log(cache.size); // 2;

entries()​

entries(): IterableIterator<[K, V | undefined]>;

Defined in: data-structures/base/iterable-entry-base.ts:31

Iterate over [key, value] pairs (may yield undefined values).

Returns​

IterableIterator<[K, V | undefined]>

Iterator of [K, V | undefined].

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.entries

every()​

every(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-entry-base.ts:66

Test whether all entries satisfy the predicate.

Parameters​

predicate​

EntryCallback<K, V | undefined, boolean>

(key, value, index, self) => boolean.

thisArg?​

unknown

Optional this for callback.

Returns​

boolean

true if all pass; otherwise false.

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.every

filter()​

filter(callbackfn, thisArg?): this;

Defined in: data-structures/linked-list/skip-linked-list.ts:556

Creates a new SkipList with entries that pass the predicate.

Parameters​

callbackfn​

EntryCallback<K, V | undefined, boolean>

thisArg?​

unknown

Returns​

this

Example​

// Filter entries
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [2, 'b'],
      [3, 'c']
    ]);
    const result = sl.filter((v, k) => k > 1);
    console.log(result.size); // 2;

Overrides​

IterableEntryBase.filter

find()​

find(callbackfn, thisArg?): [K, V | undefined] | undefined;

Defined in: data-structures/base/iterable-entry-base.ts:114

Find the first entry that matches a predicate.

Parameters​

callbackfn​

EntryCallback<K, V | undefined, boolean>

(key, value, index, self) => boolean.

thisArg?​

unknown

Optional this for callback.

Returns​

[K, V | undefined] | undefined

Matching [key, value] or undefined.

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.find

first()​

first(): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:309

Returns the first (smallest key) entry, or undefined if empty.

Returns​

[K, V | undefined] | undefined

Example​

// Access the minimum entry
 const sl = new SkipList<number, string>([
      [5, 'e'],
      [1, 'a'],
      [3, 'c']
    ]);
    console.log(sl.first()); // [1, 'a'];

floor()​

floor(key): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:409

Greatest entry ≤ key, or undefined.

Parameters​

key​

K

Returns​

[K, V | undefined] | undefined

Example​

// Greatest entry ≤ key
 const sl = new SkipList<number, string>([
      [10, 'a'],
      [20, 'b'],
      [30, 'c']
    ]);
    console.log(sl.floor(25)); // [20, 'b'];
    console.log(sl.floor(5)); // undefined;

forEach()​

forEach(callbackfn, thisArg?): void;

Defined in: data-structures/base/iterable-entry-base.ts:99

Visit each entry, left-to-right.

Parameters​

callbackfn​

EntryCallback<K, V | undefined, void>

(key, value, index, self) => void.

thisArg?​

unknown

Optional this for callback.

Returns​

void

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.forEach

get()​

get(key): V | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:243

Get the value for a key, or undefined if not found. Overrides base O(n) with O(log n) skip-list search.

Parameters​

key​

K

Returns​

V | undefined

Example​

// Building a sorted index
 type Product = { id: number; name: string; price: number };
    const products: Product[] = [
      { id: 1, name: 'Widget', price: 25 },
      { id: 2, name: 'Gadget', price: 50 },
      { id: 3, name: 'Doohickey', price: 15 }
    ];

    const index = new SkipList<number, Product, Product>(products, {
      toEntryFn: (p: Product) => [p.price, p]
    });

    // Iterate in sorted order by price
    const names = [...index.values()].map(p => p!.name);
    console.log(names); // ['Doohickey', 'Widget', 'Gadget'];

    // Range search: products between $20 and $60
    const range = index.rangeSearch([20, 60]);
    console.log(range.map(([, p]) => p!.name)); // ['Widget', 'Gadget'];

Overrides​

IterableEntryBase.get

has()​

has(key): boolean;

Defined in: data-structures/linked-list/skip-linked-list.ts:261

Check if a key exists. Overrides base O(n) with O(log n) skip-list search.

Parameters​

key​

K

Returns​

boolean

Example​

// Check key existence
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [3, 'c'],
      [5, 'e']
    ]);
    console.log(sl.has(3)); // true;
    console.log(sl.has(4)); // false;

Overrides​

IterableEntryBase.has

hasValue()​

hasValue(value): boolean;

Defined in: data-structures/base/iterable-entry-base.ts:143

Whether there exists an entry with the given value.

Parameters​

value​

V | undefined

Value to test.

Returns​

boolean

true if found; otherwise false.

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.hasValue

higher()​

higher(key): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:435

Least entry strictly > key, or undefined.

Parameters​

key​

K

Returns​

[K, V | undefined] | undefined

Example​

// Strictly greater entry
 const sl = new SkipList<number, string>([
      [10, 'a'],
      [20, 'b'],
      [30, 'c']
    ]);
    console.log(sl.higher(15)); // [20, 'b'];
    console.log(sl.higher(30)); // undefined;

isEmpty()​

isEmpty(): boolean;

Defined in: data-structures/linked-list/skip-linked-list.ts:131

Check if empty

Returns​

boolean

Example​

// Check if empty
 const sl = new SkipList<number, string>();
    console.log(sl.isEmpty()); // true;

Overrides​

IterableEntryBase.isEmpty

keys()​

keys(): IterableIterator<K>;

Defined in: data-structures/base/iterable-entry-base.ts:42

Iterate over keys only.

Returns​

IterableIterator<K>

Iterator of keys.

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.keys

last()​

last(): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:325

Returns the last (largest key) entry, or undefined if empty.

Returns​

[K, V | undefined] | undefined

Example​

// Access the maximum entry
 const sl = new SkipList<number, string>([
      [5, 'e'],
      [1, 'a'],
      [3, 'c']
    ]);
    console.log(sl.last()); // [5, 'e'];

lower()​

lower(key): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:459

Greatest entry strictly < key, or undefined.

Parameters​

key​

K

Returns​

[K, V | undefined] | undefined

Example​

// Strictly less entry
 const sl = new SkipList<number, string>([
      [10, 'a'],
      [20, 'b'],
      [30, 'c']
    ]);
    console.log(sl.lower(25)); // [20, 'b'];
    console.log(sl.lower(10)); // undefined;

map()​

map<MK, MV>(callback, options?): SkipList<MK, MV>;

Defined in: data-structures/linked-list/skip-linked-list.ts:531

Creates a new SkipList with entries transformed by callback.

Type Parameters​

MK​

MK

MV​

MV

Parameters​

callback​

EntryCallback<K, V | undefined, [MK, MV]>

options?​

SkipListOptions<MK, MV, [MK, MV]>

Returns​

SkipList<MK, MV>

Example​

// Transform entries
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [2, 'b']
    ]);
    const mapped = sl.map((v, k) => [k, v?.toUpperCase()] as [number, string]);
    console.log([...mapped.values()]); // ['A', 'B'];

Overrides​

IterableEntryBase.map

pollFirst()​

pollFirst(): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:347

Remove and return the first (smallest key) entry.

Returns​

[K, V | undefined] | undefined

Example​

// Remove and return smallest
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [2, 'b'],
      [3, 'c']
    ]);
    console.log(sl.pollFirst()); // [1, 'a'];
    console.log(sl.size); // 2;

pollLast()​

pollLast(): [K, V | undefined] | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:366

Remove and return the last (largest key) entry.

Returns​

[K, V | undefined] | undefined

Example​

// Remove and return largest
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [2, 'b'],
      [3, 'c']
    ]);
    console.log(sl.pollLast()); // [3, 'c'];
    console.log(sl.size); // 2;

print()​

print(): void;

Defined in: data-structures/base/iterable-entry-base.ts:203

Print a human-friendly representation to the console.

Returns​

void

Remarks​

Time O(n), Space O(n)

Inherited from​

IterableEntryBase.print

rangeSearch()​

rangeSearch(range, options?): [K, V | undefined][];

Defined in: data-structures/linked-list/skip-linked-list.ts:492

Returns entries within the given key range.

Parameters​

range​

[K, K]

options?​

SkipListRangeOptions = {}

Returns​

[K, V | undefined][]

Example​

// Find entries in a range
 const sl = new SkipList<number, string>([
      [1, 'a'],
      [2, 'b'],
      [3, 'c'],
      [4, 'd'],
      [5, 'e']
    ]);
    const result = sl.rangeSearch([2, 4]);
    console.log(result); // [
 //      [2, 'b'],
 //      [3, 'c'],
 //      [4, 'd']
 //    ];

reduce()​

reduce<U>(callbackfn, initialValue): U;

Defined in: data-structures/base/iterable-entry-base.ts:171

Reduce entries into a single accumulator.

Type Parameters​

U​

U

Parameters​

callbackfn​

ReduceEntryCallback<K, V | undefined, U>

(acc, value, key, index, self) => acc.

initialValue​

U

Initial accumulator.

Returns​

U

Final accumulator.

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.reduce

set()​

set(key, value): this;

Defined in: data-structures/linked-list/skip-linked-list.ts:194

Insert or update a key-value pair. Returns this for chaining. Unique keys only — if key exists, value is updated in place.

Parameters​

key​

K

value​

V

Returns​

this

Example​

// In-memory sorted key-value store
 const store = new SkipList<number, string>();

    store.set(3, 'three');
    store.set(1, 'one');
    store.set(5, 'five');
    store.set(2, 'two');

    console.log(store.get(3)); // 'three';
    console.log(store.get(1)); // 'one';
    console.log(store.get(5)); // 'five';

    // Update existing key
    store.set(3, 'THREE');
    console.log(store.get(3)); // 'THREE';

some()​

some(predicate, thisArg?): boolean;

Defined in: data-structures/base/iterable-entry-base.ts:83

Test whether any entry satisfies the predicate.

Parameters​

predicate​

EntryCallback<K, V | undefined, boolean>

(key, value, index, self) => boolean.

thisArg?​

unknown

Optional this for callback.

Returns​

boolean

true if any passes; otherwise false.

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.some

toArray()​

toArray(): [K, V | undefined][];

Defined in: data-structures/base/iterable-entry-base.ts:186

Converts data structure to [key, value] pairs.

Returns​

[K, V | undefined][]

Array of entries.

Remarks​

Time O(n), Space O(n)

Inherited from​

IterableEntryBase.toArray

toVisual()​

toVisual(): string | [K, V | undefined][];

Defined in: data-structures/base/iterable-entry-base.ts:195

Visualize the iterable as an array of [key, value] pairs (or a custom string).

Returns​

string | [K, V | undefined][]

Array of entries (default) or a string.

Remarks​

Time O(n), Space O(n)

Inherited from​

IterableEntryBase.toVisual

values()​

values(): IterableIterator<V | undefined>;

Defined in: data-structures/base/iterable-entry-base.ts:53

Iterate over values only.

Returns​

IterableIterator<V | undefined>

Iterator of values.

Remarks​

Time O(n), Space O(1)

Inherited from​

IterableEntryBase.values

createDefaultComparator()​

static createDefaultComparator<K>(): Comparator<K>;

Defined in: data-structures/linked-list/skip-linked-list.ts:102

Creates a default comparator supporting number, string, Date, and bigint.

Type Parameters​

K​

K

Returns​

Comparator<K>

Protected Members​

_findNode()​

protected _findNode(key): SkipListNode<K, V> | undefined;

Defined in: data-structures/linked-list/skip-linked-list.ts:603

Finds the node for a given key, or undefined.

Parameters​

key​

K

Returns​

SkipListNode<K, V> | undefined

_findUpdate()​

protected _findUpdate(key): SkipListNode<K, V>[];

Defined in: data-structures/linked-list/skip-linked-list.ts:587

Finds the update array (predecessors at each level) for a given key.

Parameters​

key​

K

Returns​

SkipListNode<K, V>[]

_getIterator()​

protected _getIterator(): IterableIterator<[K, V | undefined]>;

Defined in: data-structures/linked-list/skip-linked-list.ts:571

Underlying iterator for the default iteration protocol.

Returns​

IterableIterator<[K, V | undefined]>

Iterator of [K, V].

Remarks​

Time O(n), Space O(1)

Overrides​

IterableEntryBase._getIterator