◐ Shell
clean mode source ↗

feat: add Skip List (Data-Structures/Linked-List) by ChrisJr404 · Pull Request #1896 · TheAlgorithms/JavaScript

ChrisJr404

What

Adds a Skip List implementation under Data-Structures/Linked-List/SkipList.js with a companion test file under the existing test/ directory.

A skip list is a probabilistic ordered-set / map data structure with expected O(log n) search, insert and delete. Each newly inserted node is promoted to the next level with probability p (default 1/2), giving an expected height of log_{1/p}(n). Compared to balanced BSTs (AVL, red-black) it is much simpler to implement because there are no rotations - balance is maintained statistically rather than structurally. Its semantics also map cleanly onto a multi-level linked list, which is why it lives next to the other linked-list variants in this repo.

Reference: https://en.wikipedia.org/wiki/Skip_list

API

SkipList exposes:

  • insert(key, value?) (returns this, chainable; updates value if key exists)
  • search(key) -> value or undefined
  • has(key) -> boolean
  • delete(key) -> boolean
  • size() / isEmpty()
  • entries() generator yielding [key, value] pairs in ascending key order
  • Symbol.iterator yielding keys in ascending order

The constructor accepts { maxLevel, p, random } so the RNG can be injected for deterministic testing.

Tests

Data-Structures/Linked-List/test/SkipList.test.js adds 14 cases covering:

  • empty / size / isEmpty
  • insert + search (with and without explicit value)
  • key reinsertion updates value without growing size
  • has() membership
  • delete present / delete absent
  • ascending iteration regardless of insertion order
  • entries() output
  • string keys with lexicographic ordering
  • a 500-op randomized stress workload (deterministic LCG) cross-checked against a Set reference
  • input validation on the constructor (maxLevel, p, random)
  • behaviour under forced-min and forced-max promotion levels

Checks

  • npm run check-style clean
  • npm test -> 347 files / 11984 tests pass locally (including the 14 new ones)

DIRECTORY.md is intentionally not touched in this PR - the UpdateDirectory workflow will regenerate it on push.