trekhleb/javascript-algorithms
github.com/trekhleb/javascript-algorithms ↗ · 630 files · 1.8 MB
JavaScript Algorithms and Data Structures 🇺🇦 UKRAINE IS BEING ATTACKED BY RUSSIAN ARMY.
Overview
trekhleb/javascript-algorithms is a curated, test-driven educational collection of classic computer-science data structures and algorithms implemented in plain ES-module JavaScript, organized as ~150 self-contained topic folders under src/data-structures and src/algorithms, each paired with a README (often translated into ~20 locales) and a Jest test suite. It is not an application or published library — there is no runtime entrypoint, no index.js despite the package.json "main" field, and the only 'product' surface is the code itself plus the npm test/lint/coverage scripts. Distinctive traits: a shared Comparator/abstract-Sort callback design lets learners inject custom comparison and visiting hooks, and Jest coverage thresholds of 100% statements/functions/lines are enforced via npm run coverage in CI.
System map
The repo is a flat monorepo of independent algorithm/data-structure modules — there is no app server, CLI, or build artifact; the runtime boundary is simply Node.js >=22 running Jest 30 over ES-module sources transpiled by @babel/preset-env. Code lives in three subtrees: src/data-structures (14 categories), src/algorithms (14 topic dirs), plus src/utils and a src/playground scratch area. Cross-cutting wiring is minimal: a single shared Comparator utility and a small inheritance graph (Sort -> QuickSort et al.; Heap -> MinHeap/MaxHeap -> PriorityQueue). Quality gates are npm run lint (eslint airbnb config) on pre-commit via husky, and npm run coverage in GitHub Actions CI on Node 22.x with Codecov upload.
- There is no application entrypoint or index.js at the repo root even though package.json declares "main": "index.js"; the package is a code collection consumed by reading/importing individual modules, not a runnable or publishable artifact.
- npm scripts define the entire developer workflow: `npm run lint` (eslint ./src/**), `npm test` (jest), `npm run coverage` (jest --coverage), `npm run ci` (lint + coverage), and `prepare` installs husky hooks.
- Source is ES modules transpiled for tests by @babel/preset-env via .babelrc; there is no bundler, TypeScript, or build step.
- The code is organized into src/data-structures (linked-list, doubly-linked-list, queue, stack, deque, hash-table, heap, priority-queue, trie, tree/{avl,red-black,segment,fenwick,binary-search-tree}, graph, disjoint-set, bloom-filter, lru-cache) and src/algorithms (sorting, search, graph, tree, linked-list, math, string, sets, cryptography, image-processing, ml, statistics, stack, uncategorized).
- src/utils/comparator/Comparator.js is the single shared utility: it wraps an optional custom compare function and exposes equal/lessThan/greaterThan/lessThanOrEqual/greaterThanOrEqual/reverse, and is injected into LinkedList, Heap, Sort, and PriorityQueue constructors.
- A small inheritance hierarchy provides shared structure: abstract Heap throws if constructed directly and is extended by MinHeap and MaxHeap; PriorityQueue extends MinHeap and swaps in a priority-aware Comparator.
- The abstract Sort base class normalizes {compareCallback, visitingCallback} in initSortingCallbacks and forces subclasses to implement sort() (throws 'sort method must be implemented'); QuickSort and the other 10 sorting dirs subclass it.
- ESLint uses the airbnb preset with jest plugin and five relaxed rules (no-bitwise, no-lonely-if, class-methods-use-this, arrow-body-style, no-loop-func); a React version setting exists in .eslintrc despite the repo containing no React code.
- GitHub Actions CI (.github/workflows/CI.yml) runs on push/PR to master on ubuntu-latest with a Node 22.x matrix: npm i -> npm run lint -> npm run coverage -> codecov/codecov-action@v4 upload.
- Husky is wired through the `prepare` script and .husky/pre-commit runs `npm run lint` on every commit, so lint is the only client-side gate; tests are enforced only in CI.
- Engines require node >=22.0.0 and npm >=10.0.0; devDependencies are limited to babel, eslint stack, jest 30, @types/jest, husky, and pngjs (used only by the seam-carving image test).
Feature catalog
Features here are the algorithm/data-structure modules themselves — each is a self-contained folder with one default-exported function or class, a README.md (frequently translated), and a co-located test directory. The catalog spans ~30 data-structure implementations across 14 categories and ~100 algorithm implementations across 14 topics, ranging from beginner (factorial, bubble sort) to advanced (red-black tree, seam carving, k-means). There are no routes, screens, or CLI subcommands; the 'user-facing' surface is the module APIs plus the playground scratch file.
- LinkedList provides a full fluent API — prepend, append, insert(value, rawIndex), delete(value), find({value, callback}), deleteTail, deleteHead, fromArray, toArray, toString(callback), reverse — with most mutating methods returning `this` for chaining.
- Graph supports directed and undirected modes via a constructor flag, auto-adds missing vertices on addEdge, throws on duplicate vertex/edge insertion, and offers getNeighbors, findEdge, getWeight, reverse (for directed graphs), getVerticesIndices and getAdjacencyMatrix.
- HashTable implements separate-chaining collision handling by filling each of its 32 default buckets with a LinkedList and tracking keys in a parallel `keys` object for O(1) has().
- LRUCache implements O(1) get/set using a nodesMap plus an internal doubly-linked list with sentinel head/tail nodes, promote() and evict() helpers, and a hard capacity eviction; an alternative LRUCacheOnMap implementation ships alongside it.
- BloomFilter exposes insert/mayContain backed by a closed-over boolean array (createStore) and three hand-rolled hash functions (hash1/hash2/hash3), demonstrating false-positive semantics.
- Eleven sorting algorithms live under src/algorithms/sorting (bubble, bucket, counting, heap, insertion, merge, quick, radix, selection, shell) all extending the abstract Sort class and honoring compareCallback/visitingCallback hooks.
- Graph algorithms cover traversals (breadthFirstSearch, depthFirstSearch) plus articulation-points, bellman-ford, bridges, detect-cycle, dijkstra, eulerian-path, floyd-warshall, hamiltonian-cycle, kruskal, prim, strongly-connected-components, topological-sorting and travelling-salesman.
- The image-processing topic implements content-aware seam carving: resizeImageWidth shrinks an ImageData-like object width via energy-map calculation, DP lowest-energy seam finding, and in-place seam deletion.
- Math topics include factorial (iterative and recursive variants), fibonacci, primality-test, sieve-of-eratosthenes, euclidean-algorithm, fourier-transform, matrix operations, complex-number, bits manipulation and liu-hui pi approximation.
- Cryptography offers caesar-cipher, hill-cipher, rail-fence-cipher and polynomial-hash (PolynomialHash plus a SimplePolynomialHash variant) — educational ciphers, not production crypto.
- src/playground/playground.js is an explicit sandbox: it imports an algorithm (factorial by default), exposes a playground() function, and is exercised by src/playground/__test__/playground.test.js via `npm test -- 'playground'`.
- Every topic folder ships a README.md with explanations and further-reading links, and most offer translations as README.xx-XX.md files (e.g., linked-list alone has 10 locale variants).
Data flow
Data flow is simple and uniform: callers (tests or the playground) invoke a module's default export with plain JS values; the module mutates or returns in-memory structures; results are compared with Jest matchers. There is no persistence, network, or external state — the only file IO is the seam-carving test streaming PNG fixtures through pngjs. The Comparator-injection pattern and traversal callbacks are the two mechanisms that let callers steer internal behavior without subclassing.
- Inputs are plain JS values passed directly to functions/classes (e.g., factorial(number), quickSort.sort(array), linkedList.append(value)); there is no request/response, CLI parsing, or stdin handling anywhere in src/.
- Comparator is the primary data-normalization seam: constructors accept an optional compareFunction, and all ordering decisions flow through comparator.equal/lessThan/greaterThan rather than native operators.
- Sorting transforms input -> cloned array -> pivot-partitioned left/center/right arrays -> recursively sorted concatenated output; QuickSort clones the input (`[...originalArray]`) so the caller's array is never mutated.
- Traversal algorithms move data through a callback pipeline: initCallbacks builds a closed-over `seen` map for allowTraversal, then each vertex flows enterVertex -> neighbor iteration gated by allowTraversal -> leaveVertex.
- Queue is a thin adapter over LinkedList: enqueue delegates to append (tail), dequeue delegates to deleteHead (front), isEmpty checks linkedList.head — showing how data-structures compose as building blocks.
- HashTable.set flows key -> hash() (char-code sum mod bucket count) -> buckets[hash] LinkedList -> find by callback -> append or update node.value.value; get/delete follow the same path.
- Seam carving is the only flow touching the filesystem, and only in tests: pngLoad streams a .png via fs.createReadStream into pngjs, converts to an ImageData-shaped object, then resizeImageWidth mutates img.data in place while tracking a separate logical {w,h} size.
- State owners are instance fields on the structures: LinkedList.head/tail, Graph.vertices/edges (plain objects keyed by getKey()), HashTable.buckets/keys, Heap.heapContainer array, LRUCache.nodesMap/size plus sentinel nodes.
- Outputs are returned values (sorted arrays, found nodes, traversal orders accumulated by caller-supplied callbacks) plus toString() representations that tests use as the primary assertion mechanism (e.g., expect(linkedList.toString()).toBe('1,2')).
- Graph.getAdjacencyMatrix materializes a derived NxN weight matrix filled with Infinity for non-edges by iterating vertices and their neighbors — an explicit transform from adjacency-list storage to matrix output for algorithms like floyd-warshall.
Behavior traces
Three flows were traced end-to-end. (1) Test execution: npm test -> jest -> testRegex match -> test file imports module under test -> assertions on return values/toString. (2) Sorting: QuickSort construction -> Sort.initSortingCallbacks -> sort() recursion driven by Comparator and visitingCallback. (3) BFS over a graph: callback init with seen-set -> Queue enqueue/dequeue -> getNeighbors -> allowTraversal gating. A fourth flow (seam carving) shows the only IO path: PNG load -> energy map -> DP seam -> in-place pixel shift.
- Test-run trace: `npm test` invokes jest, which applies testRegex '(/__tests__/.*|(\\.|/)(test|spec))\\.jsx?$' from jest.config.js, picks up files like src/data-structures/linked-list/__test__/LinkedList.test.js, which imports ../LinkedList, which imports LinkedListNode and ../../utils/comparator/Comparator.
- Sorting trace (QuickSort): new QuickSort(callbacks) -> Sort constructor -> Sort.initSortingCallbacks fills visitingCallback stub and wraps compareCallback in Comparator -> sort(originalArray) clones array -> shift() pivot -> partition loop calls callbacks.visitingCallback and comparator.equal/lessThan -> recursive sort of left/right -> concat result.
- BFS trace: breadthFirstSearch(graph, startVertex, callbacks) -> initCallbacks builds allowTraversal closure with `seen` map -> new Queue() -> enqueue(startVertex) -> while !isEmpty: dequeue -> enterVertex -> graph.getNeighbors(currentVertex) -> allowTraversal decides enqueue -> leaveVertex -> repeat.
- DFS trace: depthFirstSearch -> initCallbacks (same seen-set pattern as BFS) -> depthFirstSearchRecursive -> enterVertex -> forEach neighbor -> allowTraversal gate -> recurse -> leaveVertex; recursion depth equals longest path, no explicit stack structure.
- Seam-carving trace: test calls pngLoad (fs.createReadStream.pipe(new PNG()).on('parsed')) to build an ImageData-shaped object -> resizeImageWidth({img,toWidth}) -> per removed column: calculateEnergyMap (getPixelEnergy of left/middle/right RGB deltas) -> findLowEnergySeam (DP seamPixelsMap then backtrack via `previous` links) -> deleteSeam (row-wise setPixel left-shift) -> return {img, size}.
- HashTable write trace: set(key,value) -> hash(key) (charCode sum % buckets.length) -> this.keys[key]=keyHash -> bucket LinkedList.find({callback: nodeValue.key===key}) -> append new {key,value} node or overwrite node.value.value.
- LinkedList deletion trace: delete(value) strips all matching head nodes in a while loop, then walks currentNode.next unlinking matches via compare.equal, finally reassigns this.tail if the tail matched — O(n) with the injected comparator deciding equality.
- LRUCache.get trace: get(key) -> nodesMap lookup -> promote(node) which evicts then re-appends the node to the tail of the doubly-linked list -> return node.val; set() appends a new node and evicts head.next when size exceeds capacity.
- CI pipeline trace: push/PR to master -> actions/checkout@v4 -> setup-node 22.x -> npm i -> npm run lint (eslint ./src/**) -> npm run coverage (jest --coverage, enforcing 100/95/100/100 thresholds) -> codecov upload.
Testing signals
Testing is the project's backbone: Jest 30 with ~112 __test__/__tests__ directories and ~178 spec files co-located beside implementations. Coverage thresholds are aspirational-strict (100% statements/functions/lines, 95% branches) but only enforced when the `coverage` script runs — plain `npm test` collects no coverage. Shared tester harnesses (SortTester, FourierTester) standardize whole algorithm families, and CI runs lint + coverage with Codecov upload on Node 22.
- Jest is configured in jest.config.js with testRegex '(/__tests__/.*|(\\.|/)(test|spec))\\.jsx?$', node_modules ignored, bail:false, verbose:false, and collectCoverage off by default.
- coverageThreshold demands 100% statements/functions/lines and 95% branches globally, but because collectCoverage is false this only bites under `npm run coverage`/`npm run ci`.
- Tests are co-located in `__test__` (singular, the dominant convention, ~112 dirs) or `__tests__` (plural, used by a few newer areas like seam-carving and matrix) directories next to the code they exercise.
- SortTester is a shared test harness exporting canned fixtures (sortedArr, reverseArr, notSortedArr, equalArr, negativeArr) plus static methods testSort, testNegativeNumbersSort, testSortWithCustomComparator, testSortStability and testAlgorithmTimeComplexity — the last uses jest.fn() to count visitingCallback invocations as a complexity proxy.
- The seam-carving spec uses a `.node.js` suffix inside a `__tests__` (plural) dir so the testRegex `__tests__/.*` alternative picks it up, and validates output against a reference PNG allowing <=10% of pixels to differ beyond a 50-value color threshold — a fuzzy image-equality assertion, not exact matching. (inferred)
- Helper files like src/algorithms/sorting/SortTester.js and src/algorithms/math/fourier-transform/__test__/FourierTester.js are deliberately named so they are NOT matched by testRegex (no .test/.spec suffix, not in a `__tests__` dir) — they exist only to be imported by real specs. (inferred)
- LinkedList.test.js exemplifies the house test style: construct the structure, call mutating methods, and assert primarily on toString() output and head/tail invariants rather than internal state.
- CI is the only place tests gate merges: the workflow runs `npm run coverage` after lint and uploads results via codecov/codecov-action@v4; the local pre-commit hook runs lint only, so a contributor can commit failing tests locally.
- The playground has its own spec asserting playground() === 120 (factorial(5)), giving contributors a sandbox that still participates in the coverage run.
- CONTRIBUTING.md codifies the 100% coverage expectation for PRs and asks contributors to run npm run lint and npm test before submitting.
Risk map
Security exposure is minimal — no network, auth, secrets, or shell-out; the only file IO is the seam-carving test reading local PNG fixtures. The real risks are correctness and maintainability quirks: deliberately simplified primitives (char-sum hash, first-element pivot), mutating APIs, a missing package entrypoint, mixed test-dir naming, and a coverage gate that only runs in CI. Educational intent means several implementations trade robustness for clarity.
- package.json declares "main": "index.js" but no index.js exists at the root, and there is no "private" flag or exports map — the package cannot actually be require()'d as published; consumers must deep-import module files.
- HashTable.hash uses a naive sum of char codes mod bucket count with a tiny default size of 32, so real-world key sets collide heavily; the code comments acknowledge this and point to polynomial hashing as the better approach.
- QuickSort shifts elements out of the array in a while loop (array.shift() is O(n) per call) and always picks the first element as pivot — clean for teaching but quadratic on already-sorted input; SortTester's sortedArr/reverseArr fixtures exercise exactly that worst case.
- Several APIs mutate in place, which can surprise consumers: Graph.reverse() deletes and re-adds every edge mutating the graph, resizeImageWidth rewrites img.data in place while reporting a smaller logical size, and LinkedList.reverse() rewrites node links.
- Graph.addVertex and addEdge throw generic Errors on duplicates ('Vertex has already been added before', 'Edge has already been added before') — callers must wrap or pre-check, and the error type gives no distinguishing subclass.
- depthFirstSearch uses unbounded recursion (depthFirstSearchRecursive), so pathological deep graphs can hit the Node call-stack limit; the iterative alternative is not provided. (inferred)
- Test-directory naming is inconsistent (`__test__` vs `__tests__`) and helper files rely on precise filename conventions to avoid being executed as specs — a misplaced rename could silently drop or break tests. (inferred)
- The only filesystem access in the codebase is the seam-carving spec's fs.createReadStream of repo-relative PNG fixtures (./src/algorithms/image-processing/seam-carving/__tests__/test-image-*.png), so tests are CWD-sensitive — running jest from another directory breaks that spec.
- Coverage enforcement (100/95/100/100) runs only via `npm run coverage` in CI; local `npm test` skips coverage and pre-commit runs only lint, so coverage regressions are caught late.
- .eslintrc carries a react version setting and airbnb's jsx-a11y plugin chain despite zero JSX/React code in the repo — dead config that could confuse tooling choices.
Extension points
The whole repo is designed as an additive catalog: a new algorithm or data structure is a new folder that plugs in via file convention, not registration. Two deliberate seams exist inside the code — constructor-injected Comparator functions and the Sort/Heap/MinHeap inheritance chain plus traversal callbacks — and CONTRIBUTING.md spells out the social conventions (one algorithm per PR, README required, 100% coverage).
- Adding an algorithm means creating src/algorithms/<topic>/<name>/<name>.js with a default export plus a __test__ directory; no index file or registry needs updating — Jest discovers tests via testRegex.
- New sorting algorithms plug in by extending Sort: implement sort(), inherit this.comparator and this.callbacks (compareCallback, visitingCallback), then reuse SortTester.testSort/testSortStability/testAlgorithmTimeComplexity for free coverage.
- Comparator injection is the universal customization point: LinkedList, Heap, Sort and PriorityQueue all accept a compareFunction in their constructor, letting the same structures order arbitrary objects.
- Graph traversal behavior is extended through the {allowTraversal, enterVertex, leaveVertex} callback object — consumers implement cycle detection, ordering, or instrumentation without touching the traversal internals.
- Heap is intentionally abstract (new.target guard throws on direct construction) so MinHeap/MaxHeap define ordering by overriding pairIsInCorrectOrder; PriorityQueue shows a second extension axis by overriding compare wholesale.
- New heap-flavored structures can subclass MinHeap or swap in a custom Comparator, exactly as PriorityQueue does with its priorities Map.
- BloomFilter.createStore returns a closed-over storage interface ({getValue,setValue}), so the bit-array backend could be swapped without changing insert/mayContain.
- Translation is an extension surface: adding README.xx-XX.md files (root or per-topic) follows a documented locale-code convention in CONTRIBUTING.md.
- The playground (src/playground/playground.js + __test__/playground.test.js) is a designed extension point for experimentation — it already demonstrates importing an algorithm and asserting on it.
Contributor handoff
Safe mental model: this is an educational algorithm catalog, not an app — optimize for clarity and pedagogy over cleverness or performance. Before editing, read CONTRIBUTING.md, .eslintrc, jest.config.js and the target module's README. Conventions: one default export per file, file name matches export (camelCase for functions, PascalCase for classes), heavy JSDoc typedefs and explanatory comments, co-located __test__ dirs, toString()-based assertions. Verify with npm test and npm run lint; keep 100% coverage or CI fails.
- Read first: CONTRIBUTING.md (PR rules: focused one-algorithm PRs, README required, 100% coverage), jest.config.js (testRegex + thresholds), .eslintrc (airbnb + relaxed rules), and the module's own README.md for the math/intent.
- House style: every module default-exports one function or class, annotates params/returns with JSDoc (including @typedef blocks for callback shapes), and explains non-obvious steps with inline comments — match this rather than introducing terse idioms.
- Tests belong in a sibling `__test__` dir named <Module>.test.js; for shared algorithm families reuse the harness (SortTester statics) instead of duplicating fixtures.
- Run `npm test -- <pattern>` for a single module (e.g. 'playground'), `npm test` for the full suite, `npm run lint` before committing (husky does this anyway), and `npm run coverage` to check the CI gate locally.
- Node >=22 and npm >=10 are required; dependencies are dev-only — do not add runtime dependencies, and prefer plain JS over new libraries since pedagogy is the product. (inferred)
- Do not create index.js or try to 'package' the repo — the missing main entry is the status quo; consumers deep-import files like src/data-structures/linked-list/LinkedList.js. (inferred)
- Mutating methods on data structures conventionally return `this` for chaining (append/prepend/insert/reverse); preserve that contract when editing or tests asserting chains will break.
- When touching Comparator behavior, remember Comparator.reverse() mutates the compare function in place — several tests rely on reversing sort order via this mechanism.
- The seam-carving test resolves PNG fixtures relative to process CWD (./src/...), so always run jest from the repo root; new file-IO tests should follow the `__tests__` plural dir convention so testRegex matches.
- Known traps: Graph throws on duplicate addVertex/addEdge (pre-check or expect the throw), HashTable keys must be strings (hash() iterates chars), and delete() on LinkedList removes ALL matching nodes, not just the first.
Languages
| Language | Files | Share of source |
|---|---|---|
| JavaScript | 361 | 100% |
| Markdown | 259 | docs/config |
| JSON | 1 | docs/config |
| YAML | 1 | docs/config |
Start reading here
Probable source entrypoint: src/ — inferred from the directory tree and manifest, not the upstream docs.
Source roots
src/ (597 files)
Source layout — src/
| Path | Files |
|---|---|
src/algorithms/ | 100 |
src/data-structures/ | 161 |
src/playground/ | 3 |
Repository structure
| Top-level path | Files |
|---|---|
src/ | 597 |
.husky/ | 1 |
.github/ | 1 |
Docs found: CONTRIBUTING.mdREADME.md
Package
package.json — javascript-algorithms-and-data-structures v0.0.4, 11 declared dependencies.
@babel/cli@babel/preset-env@types/jesteslinteslint-config-airbnbeslint-plugin-importeslint-plugin-jesteslint-plugin-jsx-a11yhuskyjestpngjs
CI & config entrypoints
README.md— Repository readme.github/workflows/CI.yml— GitHub Actions workflowpackage.json— npm scripts: ci, coverage, lint, prepare, test
Structural health signals
Average score 8.2/10 across 96 analyzed source files; 0 hotspots surfaced.
src/algorithms/math/matrix/__tests__/Matrix.test.js— 455 lines, score 6.7 (Large file, Long function/block)src/data-structures/graph/__test__/Graph.test.js— 450 lines, score 6.7 (Large file, Long function/block)src/data-structures/tree/red-black-tree/RedBlackTree.js— 323 lines, score 6.7 (Deep nesting, Long function/block)
These are deterministic review leads — size, churn, and structural signals — not proof of a bug in this project.
Recent history
85293e3e2b882026-07-25 — Remove Project Backers sectione087629d2a412026-07-25 — Add links to sattelite apps (thinking and drawing)5fcf3d7136062026-07-25 — Add links to sattelite apps (thinking and drawing)0f52fbaced5d2026-06-26 — Recompute graph edge key after reverse to reflect new directiondc12f1f5da282022-07-30 — Fix graph reverse method