Choosing a data structure

How to choose a structure from this toolkit — when to reach for each, what it buys, and how it differs from its alternatives. Companion to the Backgrounder, which explains how the structures work; this page is about which one to use.

Start with the defaults

Plain arrays and Map/Set win most of the time: contiguous memory, engine-optimized, zero dependencies on anything. The structures below earn their place when one of these triggers appears in your problem:

• Stable identity + O(1) surgery — insert/remove/move mid-sequence without shifting, reindexing, or invalidating references → the list family.
• One object in several collections at once, without wrapper allocations → intrusive structures: node-based lists, IndexedHeap.
• "Give me the smallest next" → the heap family.
• Ordered iteration and nearest-value queries → ordered containers.
• Bounded memory with automatic eviction → caches.

Sequences: the list family

Reach for a linked list when you splice — insert, remove, or move elements mid-sequence in O(1); when node identity must survive mutations (a reference to a node stays valid no matter what happens around it); or when one object must thread through several sequences at once. Skip it when you need random access by index or tight iteration over many small values — arrays are contiguous and cache-friendly, lists are pointer-chasing.

Two axes pick the class (the Backgrounder explains all four):

• Node-based vs value-based. Node-based (List, SList) injects links directly into your objects — zero wrappers, zero allocation per insert, and the toolkit's founding trick: custom link names (nextName/prevName) let the same object belong to several lists simultaneously (see Backgrounder § Origin). Value-based (ValueList, ValueSList) wraps arbitrary values in nodes for you — use it when elements are primitives or shouldn't be touched.
• DLL vs SLL. Doubly linked gives backward traversal and O(1) removal anywhere; singly linked halves the link memory and still gets pushBack and O(1) front ops from the circular design — its previous-node problem is solved by pointers.

Headless (Ext*) variants are views into existing circular chains — reach for them when interoperating with lists you don't own.

Bulk value pipelines: when a sequence is just values flowing through — fill, iterate, drain, no mid-sequence surgery — the UnrolledList stores them in chunked arrays: one allocation per 64 values, contiguous iteration, no growth copies. Measured ~2.6× faster than ValueList on that pattern (bench/bench-unrolled.js); RingBuffer is faster still when growth-copy spikes are acceptable.

Sorted flavors: keep a list sorted with insertSorted (O(n) per insert — fine for small or occasional), zip two sorted lists with mergeSorted (O(n + m), stable), or sort in bulk — the stable natural merge sort is O(n) on nearly-sorted input. If you find yourself inserting into sorted order constantly at scale, that's a SkipList.

Queue, Stack, and Deque

Queue, Stack, and Deque are thin adapters over ValueList. Reach for them when the collection is large or long-lived — a list-backed queue never pays Array.prototype.shift's O(n), and never reallocates. Deque adds O(1) operations at both ends, Array-parity aliases (push/pop/shift/unshift), and Python-style rotate(n) — the natural fit for sliding windows and round-robin scheduling.

RingBuffer is the throughput pick. It shares the Deque API on a circular array — contiguous, allocation-free at steady state — and measured ~5× faster than both a plain Array and the list-backed deque on steady-state queue churn (bench/bench-queues.js: 135μs vs ~690μs per 10k push+shift pairs at size 1k). It adds O(1) at(index) random access and a bounded {capacity: N} mode that evicts from the opposite end — a ready-made "keep the last N" sliding window. Choose the list-backed Deque instead when node identity matters (references into the sequence must survive mutations) or when you splice lists in and out; choose the ring for raw queue/deque work.

Honest baseline: for short-lived queues under a few hundred elements, a plain array with push/shift is simpler and fast enough; the structures above take over as size and lifetime grow.

Priority queues: the heap family

You need	Reach for
Push / pop-min, as fast as possible	MinHeap
Cancel / reschedule elements, honest O(1) membership	IndexedHeap
O(1) merge of whole queues, decrease-key by handle	PairingHeap
A simple merge heap	SkewHeap (or LeftistHeap)
Ordered visibility of everything pending	SkipList (popFront = extract-min)
Tick-driven timers: O(1) schedule/cancel/reschedule	TimerWheel

• MinHeap is the default. Array-based, cache-friendly — measured ~2–4× faster than the node-based heaps on a raw push/pop cycle (bench/bench-heaps.js: 0.97ms vs 1.91–3.88ms per 10k). Also ships static helpers operating on plain arrays. Its one weakness: finding an arbitrary element is an O(n) scan.
• IndexedHeap fixes exactly that: it stamps each element's position onto the element (configurable property name — the intrusive trick again), buying O(1) has/findIndex and O(log n) update/remove by element. The scheduler's heap: reschedule = mutate priority + update(el); cancel = remove(el). Elements must be objects.
• PairingHeap when merging queues is a primary operation (O(1) meld — cheapest in the family) or when you want decrease-key handles without touching your elements: push returns the node, values stay arbitrary. Handles are unvalidated — IndexedHeap is the honest-membership option. On the raw push/pop cycle SkewHeap is now the fastest of the node-based trio (iterative merge), but it has no handle operations.
• LeftistHeap / SkewHeap — the classic merge heaps; simpler than pairing, no handle operations. Prefer PairingHeap unless you specifically want their structure.
• Timers: the TimerWheel is the O(1)-everything scheduler — schedule/cancel/reschedule in O(1), bulk expiry per tick, measured ~5× faster than the heap on schedule-and-drain (bench/bench-timers.js). Its trade: delays quantize to whole ticks and the caller drives the clock. Reach for IndexedHeap instead when priorities are exact arbitrary values or there is no natural tick to drive.

Ordered containers

	SplayTree	SkipList	sorted list
find / insert / remove	O(log n) amortized	O(log n) expected	O(n)
reads reshape the structure	via promote()	never	never
min / max	O(log n)	O(1)	O(1)
floor / ceil, range scans	✔	✔	walk
order statistics (at / indexOf)	✔ O(log n)	—	walk
split / join	✔ O(log n) amortized	—	mergeSorted ✔
worst case per op	O(n) (amortized O(log n))	O(n) (vanishingly unlikely)	O(n)

• SplayTree is adaptive: promote() moves hot items toward the root, so skewed access patterns beat the O(log n) average — the property that earned it its place as a cache and an entropy reducer for compression (Backgrounder § Origin). It splits and joins in amortized O(log n) and serves order statistics (at/indexOf) from its subtree sizes. The trade: promoting reshapes the tree (a write on a logical read), and a degenerate shape can make a single operation O(n).
• SkipList is the predictable one: expected O(log n) regardless of access pattern, reads never mutate (safe to iterate and query concurrently with finds), O(1) min/max, floor/ceil, bounded range iteration, and popFront for priority-queue duty with full ordered visibility. Default choice for read-mostly ordered data.
• Sorted lists win when n is small, when data arrives in sorted batches (mergeSorted zips two sorted lists in O(n + m), stable), or when you sort once and iterate — the natural merge sort is O(n) on nearly-sorted input.

Caches

All four policies share one API and O(1) operations — the choice is the eviction policy:

• CacheLRU — evicts the least recently used. The default: recency approximates future use for most workloads.
• CacheLFU — evicts the least frequently used (exact, frequency-bucket implementation; ties broken by LRU). Keeps long-term-hot entries that a burst of one-off traffic would flush out of an LRU; resetCounters() ages the history when popularity shifts.
• CacheSLRU — segmented LRU: entries must earn a hit to enter the protected segment, so one-shot scans can't flush the proven-hot set. The scan-resistant upgrade from plain LRU.
• CacheClock — CLOCK (second chance): reads only set a bit — the cheapest read path of the family; eviction approximates LRU at FIFO cost.
• CacheFIFO — evicts the oldest. Cheapest bookkeeping after Clock (reads touch nothing); right for streaming workloads where recency adds no signal.
• CacheRandom — evicts a random entry. Minimal state, immune to adversarial access patterns, and surprisingly competitive when eviction quality barely matters.

All six support peek(key) (read without policy side effects) and setCapacity(n) (resize with policy-correct eviction).

The cache decorator memoizes functions/methods over any of the four.

Rules of thumb

1. Start with arrays and Map — upgrade only when a trigger from the top of this page appears in your problem.
2. Constants beat asymptotics at small n. An O(n) scan of 50 elements outruns most O(log n) structures. The toolkit's structures pay off as collections grow, live long, or churn.
3. Measure on your workload — the nano-benchmark files under bench/ show the pattern; the numbers quoted on this page came from them.
4. The intrusive designs are the toolkit's spine — node-based lists and IndexedHeap trade "elements are untouched" for zero allocation and multi-collection membership. When your elements are your own objects, that trade is usually free (Backgrounder § Origin).
5. Object pooling is a GC tool, not a throughput tool. A FreeList recycling nodes measured ~15% slower than fresh allocation on a raw churn microbench — modern engines allocate that fast. Reach for it to tame GC pauses and heap churn in long-running, latency-sensitive processes, and measure in the real workload.