| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
Codecov Report❌ Patch coverage is 99.35691% with 2 lines in your changes missing coverage. Please review.
@@ Coverage Diff @@
## master #1896 +/- ##
==========================================
+ Coverage 85.91% 86.12% +0.20%
==========================================
Files 379 380 +1
Lines 19778 20089 +311
Branches 3016 3068 +52
==========================================
+ Hits 16993 17302 +309
- Misses 2785 2787 +2 ☔ View full report in Codecov by Sentry.
|
Sorry, something went wrong.
| Back | FazBrowse Home | New Git URL |
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:
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:
Checks
DIRECTORY.md is intentionally not touched in this PR - the UpdateDirectory workflow will regenerate it on push.