data-structure-typed

English | 简体中文

A production-ready TypeScript data structures library featuring Heap, Linked List, Deque, Trie, Graph, Red-Black Tree, TreeMap, TreeSet, SkipList, Segment Tree, and more — with APIs that align with JavaScript's native Array, Map, and Set. Zero dependencies. Type-safe. ES2025 Set operations. O(log n) rank & range queries.

Looking for a TreeMap, TreeSet, or PriorityQueue in TypeScript/JavaScript? Familiar API, set operations, rank queries, sorted access — no more repeated Array.sort().

📦 Installation • 🎮 Playground • ⚡ Quick Start • 📖 Docs • 📋 API • 💡 Examples • ❓ FAQ

1. Installation
2. Playground
3. Quick Start
4. Who Should Use This?
5. Why Not Just Array or Map?
6. Key Features
7. Data Structures
8. Documentation
9. FAQ

npm i data-structure-typed

yarn add data-structure-typed

pnpm add data-structure-typed

Import only what you need — bundlers automatically tree-shake unused code:

// Full bundle — everything available
import { RedBlackTree, Deque, HashMap } from 'data-structure-typed';

// Subpath — smaller bundle, only loads the category you need
import { RedBlackTree, TreeMap, AVLTree } from 'data-structure-typed/binary-tree';
import { Deque, Queue } from 'data-structure-typed/queue';
import { HashMap } from 'data-structure-typed/hash';
import { Heap, MinHeap } from 'data-structure-typed/heap';
import { Trie } from 'data-structure-typed/trie';
import { Stack } from 'data-structure-typed/stack';
import { DoublyLinkedList } from 'data-structure-typed/linked-list';
import { DirectedGraph } from 'data-structure-typed/graph';
import { Matrix } from 'data-structure-typed/matrix';
import { MinPriorityQueue } from 'data-structure-typed/priority-queue';

Note: With "sideEffects": false and modern bundlers (Vite, Webpack 5, Rollup), even the full import from 'data-structure-typed' will tree-shake unused structures. Subpath imports give you explicit control and faster IDE autocomplete.

Standalone packages are also available:

npm i avl-tree-typed bst-typed heap-typed

Try it instantly:

• Node.js TypeScript
• Node.js JavaScript
• React TypeScript
• NestJS

If you are building ranked collections, scheduling queues, or sorted data structures in TypeScript,
consider data-structure-typed instead of hand-rolled Arrays or Maps.

• Leaderboards & Rankings — Maintain top-K efficiently without repeated sorting
• Task Scheduling — Priority queues, ordered execution, time-based operations
• Real-Time Dashboards — Grafana-style workloads with instant lookups
• Time-Series Data — Sorted insertion + fast range queries
• Search & Autocomplete — Prefix matching at scale
• Graph Problems — Pathfinding, cycle detection, topological sorting

// ❌ WITHOUT data-structure-typed
const queue = [1, 2, 3, ..., 100000
]
;
for (let i = 0; i < 100000; i++) {
  queue.shift();  // O(n) - Reindexes EVERY element!
}
// Time: 2829ms ❌

// ✅ WITH data-structure-typed (Deque)
const deque = new Deque([1, 2, 3, ..., 100000])
;
for (let i = 0; i < 100000; i++) {
  deque.shift();  // O(1) - Just moves a pointer
}
// Time: 5.83ms ✅
// **484x faster!**

• Optimized for V8 hot paths (see PERFORMANCE.md for measured benchmarks)

  • Repeated Array.shift() O(n) → Deque O(1)
  • Frequent update + keep-sorted workflows → RedBlackTree O(log n) operations
  • Avoid repeated Array.sort() if you must maintain sorted order after each update

• Optimized for V8 JIT (Node.js 18+, modern browsers)

• Tree-shakable ESM / CJS / legacy builds

📊 Full benchmarks → | Interactive report →

Don't learn new APIs. Just use push, pop, map, filter, and reduce everywhere.

// All linear structures use THE SAME 4 methods
const deque = new Deque([1, 2, 3]);
const queue = new Queue([1, 2, 3]);
const doublyLinkeList = new DoublyLinkedList([1, 2, 3]);
const singlyLinkedList = new SinglyLinkedList([1, 2, 3]);

// They ALL support:
structure.push(item);          // Add to end
structure.pop();               // Remove from end
structure.shift();             // Remove from start
structure.unshift(item);       // Add to start

Full generics and strict TypeScript support out of the box.

const tree = new RedBlackTree<number, string>();
tree.set(1, 'Alice');
tree.set(2, 'Bob');

// Type-safe access
const value = tree.get(1);  // Type: string | undefined

Works everywhere. Spread it [...], loop it for..of, convert it instantly. Pass raw data with toEntryFn/toElementFn — no pre-processing needed.

// All data structures work with iterator protocol
const tree = new RedBlackTree([5, 2, 8]);
const sorted = [...tree];              // Spread operator
for (const item of tree) {
}           // for...of loop
const set = new Set(tree);             // Set constructor

// Pass raw data directly
const map = new TreeMap(users, { toEntryFn: u => [u.id, u.name] });

Got raw objects? Three ways to use them — pick based on what you want to store:

interface User {
  id: number;
  name: string;
}

const users: User[] = [
  { id: 3, name: 'Charlie' },
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' }
];

// 1. Extract a field — store only that field
const ids = new TreeSet<number, User>(
  users,
  { toElementFn: u => u.id }
);
// [1, 2, 3] — numbers only, original objects not kept

// 2. Store full objects — sort by a field
const fullSet = new TreeSet<User>(
  users,
  { comparator: (a, b) => a.id - b.id }
);
// [{ id: 1, name: 'Alice' }, { id: 2, ... }, { id: 3, ... }]

// 3. Split into key-value — field as key, anything as value
const map = new TreeMap<number, User, User>(
  users,
  { toEntryFn: u => [u.id, u] }
);
// map.get(1) → { id: 1, name: 'Alice' }

Works across all data structures — toElementFn for single-value types (Heap, Queue, Stack, LinkedList, Trie), toEntryFn for key-value types (TreeMap, HashMap, SkipList), and comparator for any sorted structure.

✅ When you need:

• Top-K / Leaderboard queries without repeated sorting
• Insertion order + lookup performance simultaneously
• Priority queues with fast position-based access
• Time-series data with range queries
• Red-Black Tree / Heap performance without learning new APIs
• Pass raw objects directly — no .map() pre-processing needed (unique to this library in JS/TS)

✅ When your current code has:

• array.sort() in hot paths (request handlers, loops)
• Manual index tracking after insertions
• Array.shift() on large lists (queues)
• Custom sorting logic you repeat across files
• Map that needs to be ordered
• .map() calls just to reshape data before putting it in a collection

import { RedBlackTree } from 'data-structure-typed';

// Descending comparator — highest scores first
const leaderboard = new RedBlackTree<number, string>([
  [100, 'Alice'],
  [85, 'Bob'],
  [92, 'Charlie']
], { comparator: (a, b) => b - a });

// Top-2 via lazy iterator — O(k log n), no array copy
const iter = leaderboard.entries();
const { value: [topScore, topPlayer] } = iter.next();
console.log(`${topScore}: ${topPlayer}`); // 100: Alice

// Update score — O(log n)
leaderboard.delete(85);
leaderboard.set(95, 'Bob');

// Range query — players scoring 90~100, O(log n + k)
const scores90to100 = leaderboard.rangeSearch([90, 100]);
// [100, 95, 92] — automatically respects tree order

// For O(log n) top-k, rank, and pagination → see Order-Statistic Tree below

import { RedBlackTree } from 'data-structure-typed';

const tree = new RedBlackTree<number, string>([
  [100, 'Alice'], [85, 'Bob'], [92, 'Charlie'],
  [78, 'Diana'], [95, 'Eve']
], { comparator: (a, b) => b - a, enableOrderStatistic: true });

// select(k) — find k-th element, O(log n)
tree.getByRank(0);              // 100 (1st in tree order)
tree.getByRank(2);              // 92  (3rd in tree order)

// rank(key) — count elements preceding key in tree order, O(log n)
tree.getRank(92);               // 2 (2 elements before 92 in tree order)

// rangeByRank — pagination, O(log n + k)
tree.rangeByRank(0, 2);      // [100, 95, 92] — top 3

// Also works with TreeMap, TreeSet, TreeMultiMap, TreeMultiSet

import { MaxPriorityQueue } from 'data-structure-typed';

const taskQueue = new MaxPriorityQueue<{priority: number; task: string}>([], {
  comparator: (a, b) => b.priority - a.priority
});

taskQueue.add({ priority: 5, task: 'Email' });
taskQueue.add({ priority: 9, task: 'Alert' });  // Instant priority handling

const nextTask = taskQueue.pop();  // { priority: 9, task: 'Alert' }

import { TreeSet } from 'data-structure-typed';

const a = new TreeSet([1, 2, 3, 4, 5]);
const b = new TreeSet([3, 4, 5, 6, 7]);

[...a.union(b)];               // [1,2,3,4,5,6,7]
[...a.intersection(b)];        // [3,4,5]
[...a.difference(b)];          // [1,2]
[...a.symmetricDifference(b)]; // [1,2,6,7]
a.isSubsetOf(b);               // false

// Works with any Iterable — native Set, arrays, generators
a.intersection(new Set([2, 4, 6]));  // TreeSet [2, 4]

import { Deque } from 'data-structure-typed';

const queue = new Deque([1, 2, 3, 4, 5]);
queue.shift();  // Remove from front: O(1) not O(n)
queue.push(6);  // Add to back: O(1)

👉 See all 20+ structures → | Full API docs →

1. CONCEPTS.md - Core Fundamentals & Theory

• Big Three Concepts (BST, Balanced Trees, Heap)
• 13 Plain Language Explanations
• Iterator Protocol Design
• 5 Comparisons with Native JavaScript
• Complete Decision Guide

2. API Docs - Full API Reference (TypeDoc)

• Complete method signatures, parameters, return types
• Real-world @example code for every method
• Inheritance hierarchy and type details

3. OVERVIEW.md - Data Structures Overview

• Quick Reference Table
• All 20+ Structures with Examples
• CRUD Operations
• Common Methods
• TypeScript Support

4. ARCHITECTURE.md - Design & Implementation

• Design Philosophy & Principles
• 3 Pain Points Solved
• Why Deque is 484x Faster
• Iterator Protocol Design
• Self-Balancing Strategy
• V8 JIT Optimizations

5. PERFORMANCE.md - Benchmarks & Comparisons

• Performance Summary
• 3 Real-World Scenarios
• Detailed Benchmarks
• When to Use What
• Optimization Tips

6. GUIDES.md - Real-World Examples

• 4 Design Patterns
• 5 Production Code Examples
• Common Mistakes
• Best Practices

7. INTEGRATIONS.md - Framework Integration

• React Integration (State Management, Leaderboard)
• Express Integration (LRU Cache, Rate Limiting)
• Nest.js Integration (Ranking Service, Task Queue)
• TypeScript Configuration

class LRUCache<K, V> {
  private cache = new Map<K, V>();
  private order = new DoublyLinkedList<K>();

  get(key: K): V | null {
    if (!this.cache.has(key)) return null;
    // Move to end (recently used)
    // Efficient with O(1) operations
    return this.cache.get(key)!;
  }
}

type Player = {
  id: string;
  name: string;
  score: number;
};

const seedPlayers: Player[] = [
  { id: 'player_01HZX4E8Q2K8Y3J9M7T1A6B3C4', name: 'Pablo', score: 65 },
  { id: 'player_01HZX4E9R6V2D8K1P0N5S4T7U8', name: 'Bunny', score: 10 },
  { id: 'player_01HZX4EA3M9Q7W1E2R8T6Y5U0I', name: 'Jeff', score: 99 },
];

class ScoreLeaderboard {
  private readonly byScore: RedBlackTree<number, Player, Player>;

  constructor(initialPlayers: Player[]) {
    this.byScore = new RedBlackTree<number, Player, Player>(initialPlayers, {
      isMapMode: false,// Use "node value" storage rather than Map-style.
      toEntryFn: (player) => [player.score, player], // Convert a player object into the tree entry: key = score, value = player.
    });
  }

  /**
   * Returns players whose scores fall within the given range.
   * Supports either a tuple [min, max] or a Range object for inclusive/exclusive bounds.
   */
  public findPlayersByScoreRange(range: [number, number] | Range<number>): (Player | undefined)[] {
    return this.byScore.rangeSearch(range, (node) => node.value);
  }
  
  public upsertPlayer(player: Player) {
    return this.byScore.set(player.score, player);
  }
}

const leaderboard = new ScoreLeaderboard(seedPlayers);

console.log(leaderboard.findPlayersByScoreRange([65, 100]));

leaderboard.upsertPlayer({
  id: 'player_01HZX4EB7C4N2M9Q8R1T3Y6U5I',
  name: 'Alex',
  score: 80,
});

console.log(leaderboard.findPlayersByScoreRange(new Range(65, 100, true, true)));

type Message = {
  id: string;
  type: string;
  payload: unknown;
  priority: 'urgent' | 'normal';
  createdAt: number;
  retryCount?: number;
};

class MessageQueue {
  private urgent = new Deque<Message>();
  private normal = new Deque<Message>();

  dequeue(): Message | null {
    return this.urgent.shift() || this.normal.shift();
  }
}

👉 More examples in GUIDES.md

• Price-sorted order book
• Real-time portfolio rankings
• Option chain ordering

• Player leaderboards
• Enemy priority queues
• Game event scheduling

• Trending posts (top-K)
• Feed ordering
• Notification scheduling

• Patient priority queues
• Appointment scheduling
• Medical record organization

• Product price ranges
• Inventory management
• Order scheduling

✅ 20+ data structures (production-ready)
✅ 50+ code examples (real-world patterns)
✅ Full TypeScript support (strict typing)
✅ Performance benchmarks (484x speedups)
✅ Framework integrations (React, Express, Nest.js)
✅ 6 core documentation files (2500+ lines)

npm i data-structure-typed

import { RedBlackTree, Deque, MaxPriorityQueue } from 'data-structure-typed';

const tree = new RedBlackTree([5, 2, 8]);
console.log([...tree]);  // [2, 5, 8] - Automatically sorted!

Need frequent head/tail operations?
  → Deque (O(1) shift/unshift/push/pop)

Need sorted + fast lookup?
  → RedBlackTree (O(log n) guaranteed)

Need highest/lowest priority?
  → Heap/PriorityQueue (O(log n) add/remove)

Need prefix/text matching?
  → Trie (O(m+k) where m=prefix)

Need graph operations?
  → DirectedGraph/UndirectedGraph

Need range queries on array (sum/min/max)?
  → SegmentTree (any merge op) or BinaryIndexedTree (prefix sums only)

Need sorted key-value with same API as TreeMap?
  → SkipList (O(log n) avg, probabilistic balancing)

Otherwise?
  → Use Array (simplest case)

Found a bug? Have suggestions? Open an issue

MIT

README.md (this file)
docs/
├── CONCEPTS.md (theory & fundamentals)
├── OVERVIEW.md (Data structures overview)
├── ARCHITECTURE.md (design principles)
├── PERFORMANCE.md (benchmarks)
├── GUIDES.md (real-world examples)
└── INTEGRATIONS.md (framework guides)

Just started? → Quick Start

Need concepts? → CONCEPTS.md

Want to build? → GUIDES.md

Need API? → API Docs | Overview

Curious about performance? → PERFORMANCE.md

Framework questions? → INTEGRATIONS.md

Ready to supercharge your TypeScript data structures? Get started now →

Not natively. JavaScript's Map and Set are hash-based (unordered). This library provides TreeMap and TreeSet backed by Red-Black Trees — offering sorted iteration, floor/ceiling/higher/lower lookups, and getRank/getByRank/rangeByRank queries.

When you need to repeatedly access the smallest or largest element. Sorting an array is O(n log n) every time; a Heap gives you O(log n) insert and O(1) access to the top element. Use Heap, MinHeap, or MaxHeap for priority queues, top-k problems, and scheduling.

Yes. Enable with { enableOrderStatistic: true } on any tree-based structure (RedBlackTree, TreeMap, TreeSet, etc.):

• getRank(key) — how many elements precede this key in tree order
• getByRank(k) — get the element at position k
• rangeByRank(start, end) — get all elements between two positions

For ordered insert + lookup: yes. Array insert into sorted position is O(n) (shift elements). Red-Black Tree insert is O(log n). For 10,000+ elements, the difference is significant. See PERFORMANCE.md for benchmarks.

Yes. The library ships ESM, CJS, and UMD builds. It works in Node.js, browsers, React, Vue, Angular, Next.js, and any JavaScript runtime. Zero dependencies means no compatibility concerns.

Heap, MinHeap, MaxHeap, Priority Queue, Deque, Queue, Stack, Linked List (Singly / Doubly), Red-Black Tree, AVL Tree, BST, TreeMap, TreeSet, TreeMultiMap, TreeMultiSet, SkipList, Trie, HashMap, Graph (Directed / Undirected), Segment Tree, Binary Indexed Tree (Fenwick Tree), Matrix. See full list.

Yes. 2600+ tests, 99%+ code coverage, zero dependencies, and used in production. Every release passes typecheck, lint, and full test suite.

data-structure-typed offers more data structures (20+), a unified Array-like API across all structures, tree-shakeable subpath exports, and active maintenance. See PERFORMANCE.md for benchmark comparisons.

Yes. Three patterns:

• toElementFn — extract a field, store only that (TreeSet, Heap, Queue, Stack, LinkedList, Trie)
• comparator — store full objects, sort by a field (all sorted structures)
• toEntryFn — split into key-value pairs (TreeMap, HashMap, SkipList)

See the Raw Data section for examples.

UMD bundle: ~143KB minified. With subpath imports (e.g., data-structure-typed/heap), you only load what you use — as small as 18KB for Stack, 30KB for Heap. sideEffects: false enables full tree-shaking.