@crimson-carnival/ds-js

Production-ready data structures written in TypeScript — zero dependencies, tree-shakeable, fully tested.

Features

• 9 data structures — from linked lists to graphs
• TypeScript-first — full generics, .d.ts declarations included
• Zero dependencies — no runtime deps, no bloat
• Dual format — ESM and CJS bundles via tsup
• Tree-shakeable — import only what you need
• 178 unit tests — comprehensive vitest coverage

Install

npm install @crimson-carnival/ds-js

pnpm add @crimson-carnival/ds-js

yarn add @crimson-carnival/ds-js

import { Stack, Queue, Deque, PriorityQueue, Graph, AVLTree, LRUCache } from '@crimson-carnival/ds-js'

// Stack — LIFO
const stack = new Stack<number>()
stack.push(1); stack.push(2)
stack.pop()   // → 2

// Queue — FIFO
const queue = new Queue<string>()
queue.enqueue('first'); queue.enqueue('second')
queue.dequeue()  // → 'first'

// Deque — double-ended, O(1) at both ends
const deque = new Deque<number>()
deque.pushFront(1); deque.pushBack(2)
deque.popFront()  // → 1
deque.popBack()   // → 2

// AVL Tree — self-balancing BST
const tree = new AVLTree<number>()
;[5, 3, 7, 1, 9].forEach(v => tree.insert(v))
tree.inOrder()  // → [1, 3, 5, 7, 9]
tree.search(7)  // → true

// PriorityQueue — min-heap; stable FIFO tiebreaking
interface Patient { name: string; priority: number }
const hospital = new PriorityQueue<Patient>(
  (a, b) => a.priority - b.priority,
  { stable: true }     // equal-priority → insertion order
)
hospital.enqueue({ name: 'Ana',  priority: 2 })
hospital.enqueue({ name: 'Luis', priority: 1 })  // critical
hospital.enqueue({ name: 'Eva',  priority: 2 })
hospital.dequeue()?.name  // → 'Luis'
hospital.dequeue()?.name  // → 'Ana'   (FIFO)
hospital.dequeue()?.name  // → 'Eva'   (FIFO)

// LRU Cache — fixed-capacity O(1) key-value store
const cache = new LRUCache<string, number>(3)
cache.put('a', 1); cache.put('b', 2); cache.put('c', 3)
cache.put('d', 4)  // evicts 'a' (least recently used)
cache.get('a')     // → undefined
cache.get('b')     // → 2

// Graph — adjacency-list, directed or undirected
const g = new Graph<string>(false)  // undirected
g.addEdge('A', 'B'); g.addEdge('A', 'C'); g.addEdge('B', 'D')
g.bfs('A')  // → ['A', 'B', 'C', 'D']
g.dfs('A')  // → ['A', 'B', 'D', 'C']

import { Stack, Queue, Deque, PriorityQueue, Graph, AVLTree, LRUCache } from '@crimson-carnival/ds-js'

// Stack — LIFO
const stack = new Stack()
stack.push(1); stack.push(2)
stack.pop()   // → 2

// Queue — FIFO
const queue = new Queue()
queue.enqueue('first'); queue.enqueue('second')
queue.dequeue()  // → 'first'

// Deque — double-ended, O(1) at both ends
const deque = new Deque()
deque.pushFront(1); deque.pushBack(2)
deque.popFront()  // → 1
deque.popBack()   // → 2

// AVL Tree — self-balancing BST
const tree = new AVLTree()
;[5, 3, 7, 1, 9].forEach(v => tree.insert(v))
tree.inOrder()  // → [1, 3, 5, 7, 9]
tree.search(7)  // → true

// PriorityQueue — min-heap; stable FIFO tiebreaking
const hospital = new PriorityQueue(
  (a, b) => a.priority - b.priority,
  { stable: true }     // equal-priority → insertion order
)
hospital.enqueue({ name: 'Ana',  priority: 2 })
hospital.enqueue({ name: 'Luis', priority: 1 })  // critical
hospital.enqueue({ name: 'Eva',  priority: 2 })
hospital.dequeue().name  // → 'Luis'
hospital.dequeue().name  // → 'Ana'   (FIFO)
hospital.dequeue().name  // → 'Eva'   (FIFO)

// LRU Cache — fixed-capacity O(1) key-value store
const cache = new LRUCache(3)
cache.put('a', 1); cache.put('b', 2); cache.put('c', 3)
cache.put('d', 4)  // evicts 'a' (least recently used)
cache.get('a')     // → undefined
cache.get('b')     // → 2

// Graph — adjacency-list, directed or undirected
const g = new Graph(false)  // undirected
g.addEdge('A', 'B'); g.addEdge('A', 'C'); g.addEdge('B', 'D')
g.bfs('A')  // → ['A', 'B', 'C', 'D']
g.dfs('A')  // → ['A', 'B', 'D', 'C']

API Reference

DoublyLinkedList<T>

A doubly linked list with O(1) insertion and removal at both ends. Foundation for Stack, Queue, Deque, and LRU Cache.

import { DoublyLinkedList } from '@crimson-carnival/ds-js'

| Method | Returns | Complexity | |--------|---------|------------| | push(value) | this | O(1) | | pop() | T \| undefined | O(1) | | unshift(value) | this | O(1) | | shift() | T \| undefined | O(1) | | get(index) | Node<T> | O(n) | | set(index, value) | void | O(n) | | insert(index, value) | void | O(n) | | remove(index) | T | O(n) | | removeNode(node) | T | O(1) | | findNode(predicate) | Node<T> \| undefined | O(n) | | find(predicate) | T \| undefined | O(n) | | indexOf(value) | number | O(n) | | contains(value) | boolean | O(n) | | toArray() | T[] | O(n) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) | | [Symbol.iterator]() | Iterator<T> | O(n) |

Stack<T>

LIFO stack backed by DoublyLinkedList.

import { Stack } from '@crimson-carnival/ds-js'

| Method | Returns | Complexity | |--------|---------|------------| | push(value) | void | O(1) | | pop() | T \| undefined | O(1) | | peek() | T \| undefined | O(1) | | toArray() | T[] | O(n) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) |

Queue<T>

FIFO queue backed by DoublyLinkedList with task cancellation support.

import { Queue } from '@crimson-carnival/ds-js'

| Method | Returns | Complexity | |--------|---------|------------| | enqueue(value) | void | O(1) | | dequeue() | T \| undefined | O(1) | | peek() | T \| undefined | O(1) | | cancel(predicate) | boolean | O(n) | | positionOf(predicate) | number \| undefined | O(n) | | toArray() | T[] | O(n) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) |

Deque<T>

Double-ended queue — insert and remove from both ends in O(1).

import { Deque } from '@crimson-carnival/ds-js'

| Method | Returns | Complexity | |--------|---------|------------| | pushBack(value) | void | O(1) | | pushFront(value) | void | O(1) | | popBack() | T \| undefined | O(1) | | popFront() | T \| undefined | O(1) | | peekBack() | T \| undefined | O(1) | | peekFront() | T \| undefined | O(1) | | toArray() | T[] | O(n) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) | | [Symbol.iterator]() | Iterator<T> | O(n) |

LRUCache<K, V>

Least Recently Used cache with fixed capacity. Combines a DoublyLinkedList (access order) with a Map (O(1) key lookup). When full, the least recently used entry is evicted automatically.

import { LRUCache } from '@crimson-carnival/ds-js'

| Method | Returns | Complexity | |--------|---------|------------| | get(key) | V \| undefined | O(1) | | put(key, value) | void | O(1) | | has(key) | boolean | O(1) | | delete(key) | boolean | O(1) | | entries() | [K, V][] | O(n) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) | | capacity | number | O(1) |

PriorityQueue<T>

Min-heap based priority queue. The element with the highest priority (smallest value by default) is always dequeued first.

Supports an optional stable mode that guarantees FIFO ordering among elements with equal priority — ideal for scheduling, hospital triage, and task queues.

import { PriorityQueue } from '@crimson-carnival/ds-js'

// Default min-heap
const pq = new PriorityQueue<number>()
pq.enqueue(5); pq.enqueue(1); pq.enqueue(3)
pq.dequeue()  // → 1

// Custom comparator (max-heap)
const maxHeap = new PriorityQueue<number>((a, b) => b - a)

// Stable mode — FIFO tiebreaking when priorities are equal
interface Task { label: string; priority: number }
const queue = new PriorityQueue<Task>(
  (a, b) => a.priority - b.priority,
  { stable: true }
)

| Method / Getter | Returns | Complexity | |----------------|---------|------------| | enqueue(value) | void | O(log n) | | dequeue() | T \| undefined | O(log n) | | peek() | T \| undefined | O(1) | | toArray() | T[] | O(n) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) | | stable | boolean | O(1) |

AVLTree<T>

Self-balancing binary search tree. Guarantees O(log n) insert, search, and delete by maintaining height balance (|left.height − right.height| ≤ 1) via rotations.

import { AVLTree } from '@crimson-carnival/ds-js'

// Custom comparator
const tree = new AVLTree<{ id: number }>((a, b) => a.id - b.id)

| Method | Returns | Complexity | |--------|---------|------------| | insert(value) | void | O(log n) | | search(value) | boolean | O(log n) | | delete(value) | boolean | O(log n) | | min() | T \| undefined | O(log n) | | max() | T \| undefined | O(log n) | | inOrder() | T[] | O(n) | | preOrder() | T[] | O(n) | | postOrder() | T[] | O(n) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) |

Trie

Prefix tree optimized for string operations — autocomplete, spell-checking, prefix search.

import { Trie } from '@crimson-carnival/ds-js'

| Method | Returns | Complexity | |--------|---------|------------| | insert(word) | void | O(L) | | search(word) | boolean | O(L) | | startsWith(prefix) | boolean | O(L) | | delete(word) | boolean | O(L) | | wordsWithPrefix(prefix) | string[] | O(L + k) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | size | number | O(1) |

L = word/prefix length, k = total characters in matching results

Graph<T>

Weighted adjacency-list graph with BFS and DFS traversals. Supports both directed and undirected modes.

import { Graph } from '@crimson-carnival/ds-js'

const graph = new Graph<string>(false)  // undirected
graph.addEdge('A', 'B', 5)
graph.addEdge('B', 'C', 3)
graph.bfs('A')  // → ['A', 'B', 'C']

| Method | Returns | Complexity | |--------|---------|------------| | addVertex(v) | void | O(1) | | removeVertex(v) | boolean | O(V + E) | | addEdge(u, v, weight?) | void | O(1) | | removeEdge(u, v) | boolean | O(1) | | hasVertex(v) | boolean | O(1) | | hasEdge(u, v) | boolean | O(1) | | neighbors(v) | T[] | O(deg v) | | weight(u, v) | number \| undefined | O(1) | | bfs(start) | T[] | O(V + E) | | dfs(start) | T[] | O(V + E) | | clear() | void | O(1) | | isEmpty() | boolean | O(1) | | vertexCount | number | O(1) | | edgeCount | number | O(1) | | directed | boolean | O(1) |

Complexity Overview

| Structure | Insert | Delete | Search/Access | Space | |-----------|--------|--------|---------------|-------| | DoublyLinkedList | O(1)* | O(1)* | O(n) | O(n) | | Stack | O(1) | O(1) | O(n) | O(n) | | Queue | O(1) | O(1) | O(n) | O(n) | | Deque | O(1) | O(1) | O(n) | O(n) | | LRU Cache | O(1) | O(1) | O(1) | O(n) | | Priority Queue | O(log n) | O(log n) | O(1)† | O(n) | | AVL Tree | O(log n) | O(log n) | O(log n) | O(n) | | Trie | O(L) | O(L) | O(L) | O(Σ L) | | Graph | O(1) | O(V+E) | O(1) | O(V+E) |

* At head/tail. By index is O(n).
† Peek only. Arbitrary access is O(n).

Testing

npm test             # run all 178 tests
npm run test:watch   # watch mode
npm run test:lru     # run a single suite

Building

npm run build        # ESM + CJS + .d.ts

License

MIT