SkipList
data-structure-typed / SkipList
Class: SkipList<K, V, R>
Defined in: data-structures/linked-list/skip-linked-list.ts:49
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
IterableEntryBase<K,V|undefined>
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:122
Total number of entries.
Remarks
Time O(1), Space O(1)
Returns
number
Entry count.
Overrides
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
ceiling()
ceiling(key): [K, V | undefined] | undefined;
Defined in: data-structures/linked-list/skip-linked-list.ts:771
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:219
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
clone()
clone(): this;
Defined in: data-structures/linked-list/skip-linked-list.ts:265
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
delete()
delete(key): boolean;
Defined in: data-structures/linked-list/skip-linked-list.ts:518
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
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
filter()
filter(callbackfn, thisArg?): this;
Defined in: data-structures/linked-list/skip-linked-list.ts:1111
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
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
first()
first(): [K, V | undefined] | undefined;
Defined in: data-structures/linked-list/skip-linked-list.ts:581
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:825
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
get()
get(key): V | undefined;
Defined in: data-structures/linked-list/skip-linked-list.ts:417
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
has()
has(key): boolean;
Defined in: data-structures/linked-list/skip-linked-list.ts:465
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
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
higher()
higher(key): [K, V | undefined] | undefined;
Defined in: data-structures/linked-list/skip-linked-list.ts:879
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:176
Check if empty
Returns
boolean
Example
// Check if empty
const sl = new SkipList<number, string>();
console.log(sl.isEmpty()); // true;
Overrides
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
last()
last(): [K, V | undefined] | undefined;
Defined in: data-structures/linked-list/skip-linked-list.ts:627
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:930
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:1059
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
pollFirst()
pollFirst(): [K, V | undefined] | undefined;
Defined in: data-structures/linked-list/skip-linked-list.ts:676
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:722
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
rangeSearch()
rangeSearch(range, options?): [K, V | undefined][];
Defined in: data-structures/linked-list/skip-linked-list.ts:987
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
set()
set(key, value): this;
Defined in: data-structures/linked-list/skip-linked-list.ts:329
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
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
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
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
createDefaultComparator()
static createDefaultComparator<K>(): Comparator<K>;
Defined in: data-structures/linked-list/skip-linked-list.ts:86
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:1164
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:1146
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:1130
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