collections

JavaScript Collections and Data Structures

About

This is a collection of TypeScript data structures and algorithms. The goal is to provide a comprehensive set of data structures and algorithms that can be used in TypeScript/JavaScript programs.

If you are looking for EvictingCache, it has been removed as it is its own package now

Installation

// pnpm 🎉
pnpm add @d1g1tal/collections

// npm 😒
npm install @d1g1tal/collections

Usage

Both root imports and subpath imports are supported.

import { List } from '@d1g1tal/collections';
// or
import { List } from '@d1g1tal/collections/list';

TypeScript 6 Map Methods

LinkedMap, MultiMap, and SetMultiMap support the TypeScript 6 Map helper methods:

• getOrInsert(key, defaultValue)
• getOrInsertComputed(key, compute)

For LinkedMap, both methods return the map value type (V).

For MultiMap and SetMultiMap, behavior matches Map semantics:

• If the key exists, they return the existing stored collection (List<V> or Set<V>).
• If the key does not exist and you pass a scalar (V), they return that inserted scalar.
• If the key does not exist and you pass a collection (List<V> or Set<V>), they return that inserted collection.

Collection Types

| Type | Best for | Why use it | | --- | --- | --- | | List | General ordered data | Familiar array-style operations with a consistent collection API | | LinkedList | Frequent inserts/removals at the ends or middle | Avoids array shifting costs for linked-list style workflows | | LinkedMap | Ordered key/value data | Preserves order and lets you move entries to the front or back | | MultiMap | One key with many values, duplicates allowed | Stores grouped values in a List per key | | SetMultiMap | One key with many unique values | Stores grouped values in a Set per key | | Stack | LIFO workflows | Small, focused push/pop/peek abstraction | | Node | Building custom linked structures | Low-level primitive used by linked collections | | KeyedNode | Building custom keyed linked structures | Low-level node primitive for ordered key/value chains |

Choosing a Type

Use List when you want the simplest ordered collection.

Use LinkedList when inserts and removals near the front or middle matter more than random access speed.

Use LinkedMap when order is part of the behavior, such as caches, recency lists, or prioritized registries.

Use MultiMap when one key can intentionally map to repeated values.

Use SetMultiMap when one key maps to many values, but duplicates should be ignored.

Use Stack for undo history, parser state, DFS traversal, or any last-in-first-out flow.

Most users will not need Node or KeyedNode directly unless they are extending the library or building custom linked data structures.

List

Use case: maintain an ordered backlog, pipeline, or result set where indexed access and array-like operations are useful.

import { List } from '@d1g1tal/collections';

const backlog = new List(['triage', 'build', 'ship']);

backlog.add('verify');
backlog.insert(1, 'design');

console.log(backlog.get(0)); // triage
console.log(backlog.contains('ship')); // true

backlog.remove('build');

console.log(backlog.toArray());
// ['triage', 'design', 'ship', 'verify']

backlog.forEach((step) => {
	console.log(step);
});

// triage
// design
// ship
// verify

LinkedList

Use case: manage a queue, playlist, or work stream where items are frequently added or removed from either end.

import { LinkedList } from '@d1g1tal/collections';

const queue = new LinkedList();

queue.addLast('job-1');
queue.addLast('job-2');
queue.addFirst('urgent-job');

console.log(queue.getFirst()); // urgent-job
console.log(queue.getLast()); // job-2

queue.removeFirst();
queue.insert(1, 'job-1.5');

console.log(queue.toArray());
// ['job-1', 'job-1.5', 'job-2']

for (const job of queue) {
	console.log(job);
}

// job-1
// job-1.5
// job-2

Doubly Linked List

Use case: the same linked-list workflow as above, but better suited for reversing or traversing large lists where bidirectional links are beneficial.

import { LinkedList } from '@d1g1tal/collections';

const timeline = new LinkedList(LinkedList.Type.Doubly);

timeline.addLast('draft');
timeline.addLast('review');
timeline.addLast('published');

timeline.reverse();

console.log(timeline.toArray());
// ['published', 'review', 'draft']

console.log(timeline.get(1)); // review

LinkedMap

Use case: keep items in a meaningful order and promote or demote entries without rebuilding the map.

import { LinkedMap } from '@d1g1tal/collections';

const recentFiles = new LinkedMap();

recentFiles.addLast('README.md', '/docs/readme');
recentFiles.addLast('package.json', '/package');
recentFiles.addLast('tsconfig.json', '/tsconfig');

recentFiles.moveToLast('README.md');

console.log(Array.from(recentFiles.keys()));
// ['package.json', 'tsconfig.json', 'README.md']

console.log(recentFiles.getFirst()); // /package
console.log(recentFiles.getLast()); // /docs/readme

const changelogPath = recentFiles.getOrInsert('CHANGELOG.md', '/docs/changelog');
console.log(changelogPath); // /docs/changelog

const packagePath = recentFiles.getOrInsertComputed('package.json', (key) => `/${key}`);
console.log(packagePath); // /package

MultiMap

Use case: group several values under the same key when duplicates and insertion order matter.

import { List, MultiMap } from '@d1g1tal/collections';

const ticketsByStatus = new MultiMap();

ticketsByStatus.set('open', 'INC-100');
ticketsByStatus.set('open', 'INC-101');
ticketsByStatus.set('open', 'INC-101');

console.log(Array.from(ticketsByStatus.get('open') ?? []));
// ['INC-100', 'INC-101', 'INC-101']

console.log(ticketsByStatus.hasValue('open', 'INC-101')); // true

ticketsByStatus.deleteValue('open', 'INC-100');

console.log(Array.from(ticketsByStatus.get('open') ?? []));
// ['INC-101', 'INC-101']

const insertedTicket = ticketsByStatus.getOrInsert('pending', 'INC-200');
console.log(insertedTicket); // INC-200
console.log(Array.from(ticketsByStatus.get('pending') ?? []));
// ['INC-200']

const existingPending = ticketsByStatus.getOrInsert('pending', 'INC-201');
console.log(Array.from(existingPending));
// ['INC-200']

const waitingList = ticketsByStatus.getOrInsertComputed('waiting', () => new List(['INC-300', 'INC-301']));
console.log(Array.from(waitingList));
// ['INC-300', 'INC-301']

SetMultiMap

Use case: model one-to-many relationships where duplicate values should be ignored automatically.

import { SetMultiMap } from '@d1g1tal/collections';

const rolesByUser = new SetMultiMap();

rolesByUser.set('jason', 'admin');
rolesByUser.set('jason', 'editor');
rolesByUser.set('jason', 'editor');

console.log(Array.from(rolesByUser.get('jason') ?? []));
// ['admin', 'editor']

console.log(rolesByUser.hasValue('jason', 'admin')); // true

rolesByUser.deleteValue('jason', 'admin');

console.log(Array.from(rolesByUser.get('jason') ?? []));
// ['editor']

const insertedRole = rolesByUser.getOrInsert('alice', 'viewer');
console.log(insertedRole); // viewer
console.log(Array.from(rolesByUser.get('alice') ?? []));
// ['viewer']

const existingAlice = rolesByUser.getOrInsertComputed('alice', () => 'admin');
console.log(Array.from(existingAlice));
// ['viewer']

const teamRoles = rolesByUser.getOrInsertComputed('team', () => new Set(['maintainer', 'reviewer']));
console.log(Array.from(teamRoles));
// ['maintainer', 'reviewer']

Stack

Use case: represent undo history, nested parser state, or any last-in-first-out control flow.

import { Stack } from '@d1g1tal/collections';

const undoStack = new Stack();

undoStack.push('insert line');
undoStack.push('rename symbol');
undoStack.push('delete block');

console.log(undoStack.peek()); // delete block
console.log(undoStack.pop()); // delete block
console.log(undoStack.pop()); // rename symbol
console.log(undoStack.size); // 1

Low-Level Primitives

Node and KeyedNode are exposed for advanced use cases.

Use Node when you want to build your own linked structure with previous, next, and value references.

Use KeyedNode when you need the same linked behavior plus a stored key for ordered key/value structures.

Most application code should prefer LinkedList or LinkedMap over working with nodes directly.