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.

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)

• MinHeap is the default. Array-based, cache-friendly — measured ~3× faster than the node-based heaps on a raw push/pop cycle (bench/bench-heaps.js: 0.98ms vs 2.75–3.97ms 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. Measured fastest of the node-based trio. Handles are unvalidated — IndexedHeap is the honest-membership option.
• LeftistHeap / SkewHeap — the classic merge heaps; simpler than pairing, no handle operations. Prefer PairingHeap unless you specifically want their structure.
• Timers at very large scale: the classic alternative is a hashed timer wheel (O(1) schedule/cancel/tick) — not in the toolkit; MinHeap/IndexedHeap serve well into the hundreds of thousands of pending timers.

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
split / join	✔	—	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 also splits and joins cheaply. 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.
• CacheFIFO — evicts the oldest. Cheapest bookkeeping (reads touch nothing); right for streaming/scan 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.

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).