data-structures

A collection of production-quality data structure implementations in pure JavaScript with no dependencies. Each data structure is its own class with a consistent, ergonomic API. All classes implement [Symbol.iterator] so they work with for...of, spread, and destructuring.

Installation

npm install @calcaware/data-structures

Note: requires Node.js 12+ for ESM interop (index.mjs).

Or clone and use locally:

git clone https://github.com/calcaware/data-structures.git
npm install

Usage

CommonJS

const { LinkedList, Stack, HashMap } = require('@calcaware/data-structures');

ES Modules

import { LinkedList, Stack, HashMap } from '@calcaware/data-structures';

Individual files

const LinkedList = require('@calcaware/data-structures/src/linked-list');

Data Structures

DynamicArray

A resizable array backed by a fixed buffer that doubles on overflow and halves on underuse.

const { DynamicArray } = require('@calcaware/data-structures');

const a = new DynamicArray();
a.push(1).push(2).push(3);
a.insert(1, 99);   // [1, 99, 2, 3]
a.remove(1);       // removes 99 → [1, 2, 3]
a.get(0);          // 1
a.set(0, 10);
a.pop();           // 3
a.indexOf(2);      // 1
a.contains(10);    // true
a.toArray();       // [10, 2]
a.size;            // 2
a.capacity;        // current buffer size

LinkedList

Doubly linked list with O(1) head/tail operations and O(n/2) index access.

const { LinkedList } = require('@calcaware/data-structures');

const l = new LinkedList();
l.append(1).append(2).append(3);
l.prepend(0);         // [0, 1, 2, 3]
l.insertAt(2, 99);    // [0, 1, 99, 2, 3]
l.removeAt(2);        // removes 99
l.get(1);             // 1
l.set(1, 10);
l.indexOf(2);         // 2
l.contains(3);        // true
l.toArray();          // [0, 10, 2, 3]
l.size;               // 4
for (const v of l) console.log(v);

Stack

LIFO stack backed by a native array.

const { Stack } = require('@calcaware/data-structures');

const s = new Stack();
s.push(1).push(2).push(3);
s.peek();    // 3
s.pop();     // 3
s.size;      // 2
s.isEmpty(); // false
s.toArray(); // [2, 1]  (top to bottom)
for (const v of s) console.log(v); // top to bottom

Queue

FIFO queue using a circular buffer for O(1) enqueue and dequeue.

const { Queue } = require('@calcaware/data-structures');

const q = new Queue();
q.enqueue(1).enqueue(2).enqueue(3);
q.peek();     // 1
q.dequeue();  // 1
q.size;       // 2
q.isEmpty();  // false
q.toArray();  // [2, 3]

Deque

Double-ended queue backed by a doubly linked list. O(1) push/pop on both ends.

const { Deque } = require('@calcaware/data-structures');

const d = new Deque();
d.pushBack(2).pushFront(1).pushBack(3); // [1, 2, 3]
d.peekFront();  // 1
d.peekBack();   // 3
d.popFront();   // 1
d.popBack();    // 3
d.size;         // 1

HashMap

Hash table with separate chaining and automatic resizing at 75% load.

const { HashMap } = require('@calcaware/data-structures');

const m = new HashMap();
m.set('name', 'Alice').set('age', 30);
m.get('name');    // 'Alice'
m.has('age');     // true
m.delete('age');
m.size;           // 1
m.keys();         // ['name']
m.values();       // ['Alice']
m.entries();      // [['name', 'Alice']]
for (const [k, v] of m) console.log(k, v);

HashSet

Set backed by HashMap. O(1) average add, lookup, and delete.

const { HashSet } = require('@calcaware/data-structures');

const s = new HashSet();
s.add(1).add(2).add(2); // duplicates ignored
s.has(1);     // true
s.delete(2);
s.size;       // 1
s.values();   // [1]
for (const v of s) console.log(v);

Heap

Binary heap with a user-supplied comparator. Default is min-heap.

const { Heap } = require('@calcaware/data-structures');

// Min-heap (default)
const minH = new Heap();
[5, 3, 8, 1].forEach(v => minH.push(v));
minH.peek();  // 1
minH.pop();   // 1

// Max-heap
const maxH = new Heap((a, b) => b - a);
[5, 3, 8, 1].forEach(v => maxH.push(v));
maxH.pop();   // 8

minH.size;
minH.isEmpty();

BinarySearchTree

BST with optional custom comparator. Iterates in sorted (in-order) sequence.

const { BinarySearchTree } = require('@calcaware/data-structures');

const bst = new BinarySearchTree();
[5, 3, 7, 1, 4].forEach(v => bst.insert(v));
bst.contains(4);  // true
bst.min();        // 1
bst.max();        // 7
bst.inOrder();    // [1, 3, 4, 5, 7]
bst.preOrder();   // [5, 3, 1, 4, 7]
bst.postOrder();  // [1, 4, 3, 7, 5]
bst.remove(3);
bst.size;         // 4
for (const v of bst) console.log(v); // sorted

Tree

General N-ary tree with BFS and DFS traversal.

const { Tree } = require('@calcaware/data-structures');

const t = new Tree('root');
const a = t.root.addChild('a');
const b = t.root.addChild('b');
a.addChild('c');

t.bfs((value, node) => console.log(value)); // root, a, b, c
t.dfs((value, node) => console.log(value)); // root, a, c, b

const node = t.find('c'); // TreeNode
node.isLeaf();  // true
node.isRoot();  // false

t.root.removeChild(b);
t.toArray(); // ['root', 'a', 'c']

Graph

Adjacency-list graph supporting directed and undirected modes, BFS, DFS, and cycle detection.

const { Graph } = require('@calcaware/data-structures');

// Undirected (default)
const g = new Graph();
g.addEdge('A', 'B').addEdge('B', 'C');
g.hasEdge('A', 'B');    // true
g.hasEdge('B', 'A');    // true (undirected)
g.neighbors('B');       // ['A', 'C']
g.vertices();           // ['A', 'B', 'C']
g.hasCycle();           // false

const bfsOrder = [];
g.bfs('A', v => bfsOrder.push(v));

const dfsOrder = [];
g.dfs('A', v => dfsOrder.push(v));

g.removeEdge('A', 'B');
g.removeVertex('C');

// Directed graph
const dg = new Graph(true);
dg.addEdge('A', 'B').addEdge('B', 'C').addEdge('C', 'A');
dg.hasEdge('A', 'B');  // true
dg.hasEdge('B', 'A');  // false
dg.hasCycle();         // true

BloomFilter

Probabilistic set membership. No false negatives; controllable false positive rate.

const { BloomFilter } = require('@calcaware/data-structures');

// new BloomFilter(bitArraySize, hashFunctionCount)
const bf = new BloomFilter(10000, 4);
bf.add('apple').add('banana');
bf.has('apple');   // true  (definitely in set)
bf.has('cherry');  // false (definitely NOT in set)
bf.has('xyz');     // false or true (possible false positive)

bf.estimatedFalsePositiveRate; // e.g. 0.0002

DisjointSet

Union-Find with path compression and union by rank. O(α(n)) ≈ O(1) amortized.

const { DisjointSet } = require('@calcaware/data-structures');

const ds = new DisjointSet();
[1, 2, 3, 4, 5].forEach(v => ds.makeSet(v));
ds.union(1, 2);
ds.union(3, 4);
ds.connected(1, 2);  // true
ds.connected(1, 3);  // false
ds.union(2, 3);
ds.connected(1, 4);  // true (transitive)
ds.componentCount;   // 2
ds.find(1);          // root representative of 1's component

Trie

Prefix tree for string storage and lookup.

const { Trie } = require('@calcaware/data-structures');

const t = new Trie();
['apple', 'app', 'application', 'banana'].forEach(w => t.insert(w));
t.search('app');        // true
t.search('appl');       // false
t.startsWith('app');    // true
t.words('app');         // ['app', 'apple', 'application']
t.words();              // all words
t.delete('app');
t.size;                 // 3
for (const word of t) console.log(word);

LRUCache

Least Recently Used cache with O(1) get and put, backed by a doubly linked list + hash map.

const { LRUCache } = require('@calcaware/data-structures');

const cache = new LRUCache(3); // capacity = 3
cache.put('a', 1).put('b', 2).put('c', 3);
cache.get('a');       // 1  ('a' is now most recently used)
cache.put('d', 4);    // evicts 'b' (least recently used)
cache.has('b');       // false
cache.has('a');       // true
cache.size;           // 3
cache.capacity;       // 3
cache.keys();         // MRU → LRU order
for (const [key, value] of cache) console.log(key, value);

Running tests

npm test

License

ISC © Calcaware