TSDSA - TypeScript Data Structures & Algorithms

A high-performance TypeScript library providing essential data structures and algorithms with a focus on efficiency and type safety.

Table of Contents

• Overview
• Installation
• Performance Highlights
• Data Structures
• Algorithms
• Usage Examples
• Benchmarks
• Testing
• When to Use TSDSA vs Native JavaScript

Overview

TSDSA provides optimized implementations of fundamental computer science data structures and algorithms. While JavaScript's native methods are highly optimized for general use cases, TSDSA excels in specific scenarios where algorithmic complexity matters more than constant-factor optimizations.

Key Benefits

• Type Safety: Full TypeScript support with comprehensive type definitions
• Performance: Optimized for specific algorithmic use cases (see benchmarks)
• Correctness: Extensively tested implementations
• Educational: Clear, well-documented code for learning
• Production-Ready: Battle-tested in real-world applications

Installation

bash npm install tsdsa

bash yarn add tsdsa

bash pnpm add tsdsa

Performance Highlights

TSDSA significantly outperforms native JavaScript in these scenarios:

• Binary Search: Up to 5,238x faster than `Array.find()`
• Trie Operations: Up to 228x faster than native string filtering
• Deque Operations: Up to 279x faster than array-based queues
• DisjointSet: 2,170x faster than BFS for connectivity queries
• Memoized Fibonacci: 8,733x faster than naive recursion
• Priority Queue: 5.1x faster than sort-based approaches

Data Structures

Linear Data Structures

Stack

A Last-In-First-Out (LIFO) data structure.

Time Complexity:

• Push: O(1)
• Pop: O(1)
• Peek: O(1)

When to use:

• Function call management
• Undo/redo functionality
• Expression evaluation (parentheses matching)
• Backtracking algorithms

Performance: 1.14x faster than native `Array.push/pop` for high-frequency operations.

Deque (Double-Ended Queue)

A queue that allows insertion and deletion from both ends.

Time Complexity:

• pushFront/pushBack: O(1)
• popFront/popBack: O(1)

When to use:

• Sliding window algorithms
• Palindrome checking
• Task scheduling with priorities
• Browser history (forward/back navigation)

Performance: Up to 279x faster than `Array.unshift/shift` operations.

Queue

A First-In-First-Out (FIFO) data structure implemented using Deque.

Time Complexity:

• Enqueue: O(1)
• Dequeue: O(1)

When to use:

• BFS traversals
• Request processing
• Print queue management
• Message queues

Performance: 164x faster than `Array.push/shift` based queues.

Tree-Based Structures

Binary Search Tree (BST)

A sorted binary tree where left children are smaller and right children are larger.

Time Complexity:

• Insert: O(log n) average, O(n) worst
• Search: O(log n) average, O(n) worst
• Delete: O(log n) average, O(n) worst

When to use:

• Maintaining sorted data with frequent insertions
• Range queries
• Finding closest values

AVL Tree

A self-balancing Binary Search Tree that maintains O(log n) operations.

Time Complexity:

• Insert: O(log n)
• Search: O(log n)
• Delete: O(log n)

When to use:

• Need guaranteed O(log n) operations
• Frequent lookups with occasional insertions
• Database indexing

Performance: 1.55x faster than maintaining sorted arrays with binary search + splice.

Min Heap / Max Heap

A complete binary tree where parent nodes are smaller (min) or larger (max) than children.

Time Complexity:

• Insert: O(log n)
• Extract Min/Max: O(log n)
• Peek: O(1)
• Heapify: O(n)

When to use:

• Priority queues
• Heap sort
• Finding k-th smallest/largest elements
• Scheduling algorithms

Priority Queue

A queue where elements are served based on priority rather than insertion order.

Time Complexity:

• Enqueue: O(log n)
• Dequeue: O(log n)

When to use:

• Dijkstra's algorithm
• A* pathfinding
• Task scheduling
• Event-driven simulation

Performance: 5.1x faster than repeatedly sorting arrays.

Trie (Prefix Tree)

A tree structure for storing strings with shared prefixes.

Time Complexity:

• Insert: O(m) where m is string length
• Search: O(m)
• StartsWith: O(m)
• Autocomplete: O(m + k) where k is number of results

When to use:

• Autocomplete systems
• Spell checkers
• IP routing tables
• Dictionary implementations

Performance:

• 228x faster than `Array.some+startsWith`
• 66x faster than `Array.includes`
• 54x faster than `Array.filter` for autocomplete

Hash-Based Structures

LRU Cache

A cache that evicts the least recently used item when capacity is reached.

Time Complexity:

• Get: O(1)
• Put: O(1)

When to use:

• Web browser cache
• Database query caching
• Memory-constrained environments
• API response caching

Performance: 1.9x faster than naive Map-based implementations.

Graph Structures

Graph (Adjacency List)

A collection of nodes connected by edges, implemented with adjacency lists.

Time Complexity:

• Add Vertex: O(1)
• Add Edge: O(1)
• BFS/DFS: O(V + E)

When to use:

• Social networks
• Road networks
• Dependency resolution
• State machines

DisjointSet (Union-Find)

A data structure for tracking disjoint sets with union and find operations.

Time Complexity:

• Find: O(α(n)) ≈ O(1) with path compression
• Union: O(α(n)) ≈ O(1) with union by rank

When to use:

• Kruskal's MST algorithm
• Network connectivity
• Image segmentation
• Detecting cycles in undirected graphs

Performance: 2,170x faster than BFS for connectivity queries.

Algorithms

Sorting Algorithms

Merge Sort

A divide-and-conquer sorting algorithm that guarantees O(n log n) performance.

Time Complexity: O(n log n)
Space Complexity: O(n)

When to use:

• Guaranteed O(n log n) performance needed
• Stable sort required
• Sorting linked lists
• External sorting (large datasets)

Performance Note: Native `Array.sort()` is 3.88x faster due to highly optimized V8 implementation.

Quick Sort

An efficient divide-and-conquer sorting algorithm.

Time Complexity: O(n log n) average, O(n²) worst
Space Complexity: O(log n)

When to use:

• In-place sorting needed
• Average-case performance matters more than worst-case
• Cache-friendly sorting

Heap Sort

A comparison-based sorting algorithm using a heap.

Time Complexity: O(n log n)
Space Complexity: O(1)

When to use:

• Limited memory available
• Guaranteed O(n log n) needed
• No extra space allowed

Performance Note: Native `Array.sort()` is 5.06x faster for general use.

Counting Sort

A non-comparison integer sorting algorithm.

Time Complexity: O(n + k) where k is range
Space Complexity: O(k)

When to use:

• Small integer ranges
• Known value distribution
• Need linear time sorting

Performance: 1.29x faster than native sort for integer arrays in limited ranges.

Radix Sort

A non-comparison sorting algorithm that sorts by digit.

Time Complexity: O(d × n) where d is number of digits
Space Complexity: O(n + k)

When to use:

• Fixed-length integer keys
• String sorting with fixed length
• Sorting dates/times

Performance Note: Native sort is 1.71x faster for random integers.

Searching Algorithms

Binary Search

Efficient search in sorted arrays.

Time Complexity: O(log n)
Space Complexity: O(1)

When to use:

• Searching sorted arrays
• Finding insertion points
• Range queries

Performance:

• 655x faster than `Array.indexOf()`
• 5,238x faster than `Array.find()`

Linear Search

Sequential search through elements.

Time Complexity: O(n)
Space Complexity: O(1)

When to use:

• Small unsorted datasets
• Need to find all occurrences
• Can't sort the data

String Algorithms

KMP (Knuth-Morris-Pratt)

Efficient pattern matching algorithm.

Time Complexity: O(n + m)
Space Complexity: O(m)

When to use:

• Multiple searches for same pattern
• Need to avoid backtracking
• Long patterns

Performance Note: Native `String.indexOf()` is 18.96x faster due to hardware-optimized implementations.

Levenshtein Distance

Measures edit distance between two strings.

Time Complexity: O(m × n)
Space Complexity: O(m × n)

When to use:

• Spell checking
• DNA sequence analysis
• Fuzzy string matching
• Diff algorithms

Performance Note: Simple string comparison is 6.66x faster, but doesn't provide edit distance.

Graph Algorithms

Breadth-First Search (BFS)

Level-order graph traversal.

Time Complexity: O(V + E)
Space Complexity: O(V)

When to use:

• Shortest path in unweighted graphs
• Level-order traversal
• Finding connected components

Depth-First Search (DFS)

Deep exploration before backtracking.

Time Complexity: O(V + E)
Space Complexity: O(V)

When to use:

• Detecting cycles
• Topological sorting
• Finding strongly connected components
• Maze solving

Dijkstra's Algorithm

Finds shortest paths from a source vertex to all other vertices.

Time Complexity: O((V + E) log V) with priority queue
Space Complexity: O(V)

When to use:

• Shortest path in weighted graphs (non-negative weights)
• GPS navigation
• Network routing

Performance Note: Simple BFS is 3.57x faster for unweighted graphs.

Dynamic Programming

Fibonacci (Memoized)

Computes Fibonacci numbers with caching.

Time Complexity: O(n)
Space Complexity: O(n)

When to use:

• Need multiple Fibonacci calculations
• Demonstrate memoization
• Teaching DP concepts

Performance: 8,733x faster than naive recursion.

Number Theory

Sieve of Eratosthenes

Finds all prime numbers up to a limit.

Time Complexity: O(n log log n)
Space Complexity: O(n)

When to use:

• Finding all primes in a range
• Prime factorization preprocessing
• Number theory problems

Performance: 17.5x faster than naive isPrime checks.

Anagram Grouping

Groups words that are anagrams of each other.

Time Complexity: O(n × k log k) where k is average word length
Space Complexity: O(n × k)

When to use:

• Word games
• Linguistic analysis
• Text processing

Performance: 1.5x faster than manual Map grouping.

Usage Examples

Binary Search

typescript import { binarySearch } from 'tsdsa';

const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15]; const index = binarySearch(sortedArray, 7); console.log(index); // 3

Trie for Autocomplete

typescript import { Trie } from 'tsdsa';

const trie = new Trie(); trie.insert('apple'); trie.insert('application'); trie.insert('app');

const suggestions = trie.autocomplete('app'); console.log(suggestions); // ['app', 'apple', 'application']

Priority Queue

typescript import { PriorityQueue } from 'tsdsa';

const pq = new PriorityQueue((a, b) => a.priority - b.priority); pq.enqueue({ value: 'low', priority: 3 }); pq.enqueue({ value: 'high', priority: 1 }); pq.enqueue({ value: 'medium', priority: 2 });

console.log(pq.dequeue()); // { value: 'high', priority: 1 }

LRU Cache

typescript import { LRUCache } from 'tsdsa';

const cache = new LRUCache<string, number>(3); cache.put('a', 1); cache.put('b', 2); cache.put('c', 3); cache.put('d', 4); // 'a' is evicted

console.log(cache.get('a')); // null console.log(cache.get('b')); // 2

DisjointSet for Connectivity

typescript import { DisjointSet } from 'tsdsa';

const ds = new DisjointSet(5); ds.union(0, 1); ds.union(1, 2);

console.log(ds.connected(0, 2)); // true console.log(ds.connected(0, 3)); // false

Dijkstra's Algorithm

typescript import { Graph, dijkstra } from 'tsdsa';

const graph = new Graph(); graph.addEdge('A', 'B', 4); graph.addEdge('A', 'C', 2); graph.addEdge('C', 'B', 1);

const { distances, previous } = dijkstra(graph, 'A'); console.log(distances.get('B')); // 3 (A -> C -> B)

Benchmarks

Understanding the Results

The benchmark suite compares TSDSA implementations against native JavaScript equivalents across various scenarios. Here's what the results tell us:

Where TSDSA Excels

1. Algorithmic Complexity Wins

• Binary Search (655x-5,238x faster): O(log n) vs O(n) complexity dominates at scale
• Trie Operations (54x-228x faster): Prefix-based operations are fundamentally faster than linear scans
• DisjointSet (2,170x faster): Near-constant time connectivity checks vs O(V+E) BFS

2. Data Structure Optimizations

• Deque (164x-279x faster): O(1) operations vs O(n) array shifting
• Priority Queue (5.1x faster): O(log n) heap operations vs O(n log n) repeated sorting
• LRU Cache (1.9x faster): Optimized eviction vs manual tracking

3. Memoization & Preprocessing

• Fibonacci (8,733x faster): Cached results vs exponential recalculation
• Sieve of Eratosthenes (17.5x faster): Batch prime finding vs individual checks

Where Native JavaScript Wins

1. V8 Engine Optimizations

• Array.sort(): Highly optimized Timsort implementation with native code
• String.indexOf(): Hardware-accelerated string search with SIMD instructions

2. Simple Operations

• Array push/pop: Optimized for simple stack operations
• Direct comparisons: Native primitives are extremely fast

3. Constant Factor Differences

• Some algorithms like Merge Sort are theoretically optimal but lose to V8's constant-factor optimizations
• Native implementations benefit from JIT compilation and inline caching

When to Choose Which

| Scenario | Use TSDSA | Use Native | |----------|-----------|------------| | Binary search in sorted data | ✅ Always | ❌ Never (for large n) | | Autocomplete/prefix matching | ✅ Always | ❌ Never (at scale) | | Queue with frequent head operations | ✅ Always | ❌ Never | | Priority-based processing | ✅ Usually | ⚠️ Only for tiny datasets | | General sorting | ❌ Rarely | ✅ Always (unless specific constraints) | | String pattern matching | ❌ Rarely | ✅ Usually | | Simple stack operations | ⚠️ Comparable | ✅ Slightly faster | | Graph connectivity queries | ✅ Always (with DisjointSet) | ❌ Never (at scale) |

Running Benchmarks

bash npm run benchmark

The benchmark suite tests:

• Various input sizes (n=100 to n=1,000,000)
• Different data distributions (random, sorted, reverse-sorted)
• Multiple iterations for statistical significance
• Memory usage patterns

Testing

TSDSA includes comprehensive test coverage for all data structures and algorithms.

Running Tests

bash

Run all tests

npm test

Run with coverage

npm run test:coverage

Run specific test suite

npm test -- BinarySearch

Test Categories

1. Unit Tests

• Individual method correctness
• Edge cases (empty inputs, single elements)
• Boundary conditions

2. Integration Tests

• Combined operations
• Real-world scenarios
• Performance regression tests

3. Property-Based Tests

• Invariant checking
• Randomized input testing
• Behavioral verification

Test Coverage

All implementations maintain >95% code coverage with tests for:

• Correctness of algorithms
• Edge cases and error handling
• Performance characteristics
• Type safety

When to Use TSDSA vs Native JavaScript

Use TSDSA When:

1. Algorithmic Complexity Matters

   • Working with large datasets (n > 10,000)
   • Repeated operations where O(log n) vs O(n) matters
   • Provably optimal algorithms needed

2. Specific Data Structures Required

   • Tries for string operations
   • Disjoint sets for connectivity
   • Deques for double-ended operations
   • Priority queues for scheduling

3. Type Safety & Documentation

   • Need explicit type definitions
   • Want well-documented implementations
   • Building educational projects

4. Consistency Across Environments

   • Need predictable performance
   • Cross-platform consistency matters
   • Can't rely on V8-specific optimizations

Use Native JavaScript When:

1. General Purpose Operations

   • Sorting arbitrary data (use `Array.sort()`)
   • Simple string search (use `String.indexOf()`)
   • Basic array operations

2. Small Datasets

   • n < 1,000 elements
   • Constant factors dominate
   • V8 optimizations win

3. Simple Use Cases

   • Don't need specialized data structures
   • Built-in methods cover requirements
   • Minimizing dependencies matters

Hybrid Approach (Best Practice)

typescript // Use native for simple operations const sorted = [...array].sort((a, b) => a - b);

// Use TSDSA for algorithmic advantages import { binarySearch } from 'tsdsa'; const index = binarySearch(sorted, target); // Much faster than find()

// Use native for string basics const text = "hello world"; const hasHello = text.includes("hello");

// Use TSDSA for advanced string operations import { Trie } from 'tsdsa'; const autocomplete = new Trie(); // ... for autocomplete systems

🛠 Development

Setup

bash git clone https://github.com/pybool/tsdsa.git cd tsdsa npm install

Build

bash npm run build

Lint

bash npm run lint

Contributing

Contributions are welcome! Please read our Contributing Guide for details on:

• Code of conduct
• Development process
• Submitting pull requests
• Coding standards

Adding New Data Structures

1. Implement in `src/`
2. Add comprehensive tests
3. Add benchmarks
4. Update documentation
5. Submit PR

License

MIT © Emmanuel Eko

Acknowledgments

• Inspired by classic algorithms textbooks (CLRS, Sedgewick)
• Built with TypeScript
• Benchmarked against V8 engine optimizations

Further Reading

• Introduction to Algorithms (CLRS)
• Algorithms (Sedgewick)
• V8 Engine Optimization
• Big-O Cheat Sheet

Note: Performance numbers are from benchmarks on Node.js v20+ with V8 engine. Actual performance may vary based on:

• JavaScript engine version
• Hardware specifications
• Input data characteristics
• Memory pressure
• JIT warm-up state

For production use, always benchmark with your specific use case and data patterns.