DOCSEARCHbyAlgolia
Submit Docs

Data Structures Library

website·Indexed 30 days ago

https://data-structures-docs.vercel.app

A comprehensive collection of type-safe, zero-dependency data structure implementations for TypeScript and JavaScript. The library includes a variety of tools such as LRUCache, BiMap, Trie, SortedMap, Red-Black Tree, Binary Heap (MinHeap and MaxHeap), Priority Queue, Deque, and both singly and doubly linked lists.

Tokens
23.1K
Snippets
134
Records
145
Agent score
75%

What's inside Data Structures

  1. Core features of the data-structures library

    The library provides the following core guarantees for developers:

    • Type Safety: Full TypeScript support utilizing generics to ensure type safety and catch errors at compile time rather than runtime.
    • Zero Dependencies: The library has no external dependencies, ensuring a lightweight installation, improved security, and minimal bundle size impact (only imported modules are bundled).
    • Performance: Implementations are optimized for performance with documented time complexities and verified via comprehensive test coverage.

  2. Compare space complexity of common data structures

    Space complexity overview for various data structures:
    Data StructureSpaceNotes
    GeneralO(n)Linear in number of elements
    LinkedListO(n)Additional pointer per node
    DoublyLinkedListO(n)Two pointers per node
    TrieO(ALPHABET_SIZE × N × M)Can be large for long strings
    BiMapO(2n)Two internal maps

  3. Select a data structure for common web development scenarios

    Depending on the functional requirements of your feature, choose the following data structures for optimal performance:
    // 1. Web Browser History (Back/Forward navigation)
const history = new DoublyLinkedList<string>();
history.append('/home');
history.append('/products');

// 2. Autocomplete/Search Suggestions (Prefix search)
const trie = new Trie<number>(false); // case-insensitive
trie.insert('apple', 100);
trie.insert('application', 85);
trie.getAllWithPrefix('app'); // ['apple', 'application']

// 3. Leaderboard (Rank order maintenance)
const leaderboard = new SortedMap<number, Player>({
  comparator: (a, b) => b - a, // Descending
});

// 4. Rate Limiting (Request counts with expiration)
const rateLimiter = new LRUCache<string, number>({
  capacity: 10000,
  ttl: 60000, // 1 minute
});

// 5. Event Processing (Priority order)
const events = new PriorityQueue<Event>({
  comparator: (a, b) => a.priority - b.priority,
});

// 6. User ID <-> Username Mapping (Bidirectional lookup)
const users = new BiDirectionalMap<number, string>();
users.set(1, 'alice');
users.get(1); // 'alice'
users.getKey('alice'); // 1

  6. Implement Priority and Heap operations

    Use heaps or priority queues for scheduling and top-k problems:

    • Task Scheduling: Use PriorityQueue for a queue-like API with custom priorities.
    • K Largest/Smallest Elements: Use BinaryHeap (MinHeap or MaxHeap) for efficient top-k algorithms.
    • Median Tracking: Use a combination of one MinHeap and one MaxHeap.
    • Dijkstra's Algorithm: Use PriorityQueue for min-priority extraction.
    // Task scheduling
const scheduler = new PriorityQueue<Task>({
  comparator: (a, b) => b.priority - a.priority,
});

// K largest elements
const minHeap = new MinHeap<number>();
for (const num of numbers) {
  minHeap.insert(num);
  if (minHeap.size > k) minHeap.remove();
}

  8. Manage unique values with Sets and Red-Black Trees

    Depending on whether you need the unique values to be sorted:

    • Unsorted Unique Values: Use native JavaScript Set (Fast, O(1) duplicate checking).
    • Sorted Unique Values: Use RedBlackTree for O(log n) operations and efficient min/max access.
    // Unsorted unique values
const uniqueIds = new Set<string>();

// Sorted unique values
const sortedScores = new RedBlackTree<number>();
sortedScores.insert(85);
sortedScores.min(); // 85
sortedScores.max(); // 92

  9. Select a data structure using the Quick Decision Tree

    Use the following logic to choose a data structure based on your primary requirements:

    • Key-Value Mapping?
      • Yes $\rightarrow$ Need sorted order? $\rightarrow$ Yes: SortedMap / No: Need bidirectional lookup? $\rightarrow$ Yes: BiDirectionalMap / No: JavaScript Map (native).
    • Ordered Collection?
      • Priority-based $\rightarrow$ PriorityQueue or BinaryHeap
      • FIFO (Queue) $\rightarrow$ Queue
      • LIFO (Stack) $\rightarrow$ Array or Deque
      • Both ends $\rightarrow$ Deque
      • Sorted unique values $\rightarrow$ RedBlackTree
      • String prefix search $\rightarrow$ Trie
      • Sequential access $\rightarrow$ LinkedList or DoublyLinkedList
      • LRU caching $\rightarrow$ LRUCache

  10. Iterate and drain a Queue

    You can iterate through a queue in two ways:

    1. Forward Iteration: A non-destructive loop from front to back.
    2. Draining: The drain() method allows you to process and remove elements as you iterate. If the loop is terminated early (e.g., via break), the remaining items stay in the queue.
    // Non-destructive iteration
for (const value of queue) {
  console.log(value);
}

// Destructive iteration (draining)
for (const value of queue.drain()) {
  console.log(value);
}