UnrolledList

Unrolled linked list for values — chunked arrays strung on a doubly linked chain: one allocation per chunkSize values instead of one per value, chunk-contiguous memory for fast iteration, and no growth copies — values never move once placed. Measured ~2.6× faster than ValueList on a fill+iterate+drain pipeline.

Legend for tables

• API
  • options - an object with optional properties:
    • chunkSize - value slots per chunk. Default: 64.
  • value - the value to be stored in the list
  • values - an iterable that provides values
  • iterator - an Iterator instance or an object with an iterator/iterable protocol
• Complexity
  • O - complexity of an operation
  • O(1) - constant time (amortized for pushes that open a chunk)
  • O(n) - linear time proportional to the list size
  • O(n/c) - linear in the number of chunks (c = chunkSize)
  • O(k) - linear time proportional to the argument size

unrolled-list.js

Implementation of UnrolledList:

import UnrolledList from 'list-toolkit/unrolled-list.js';

const pipeline = new UnrolledList();
for (const item of source) pipeline.push(item); // one allocation per 64 values
for (const item of pipeline) process(item); //     chunk-contiguous iteration
while (!pipeline.isEmpty) sink(pipeline.shift());

Class UnrolledList

Methods:

Member	Return type	Description	O
constructor(options)	this	constructs a new UnrolledList	O(1)
isEmpty	boolean	checks if the list is empty	O(1)
size	number	the number of values (tracked — no walk)	O(1)
chunkSize	number	value slots per chunk	O(1)
front	value or undefined	the first value	O(1)
back	value or undefined	the last value	O(1)
peekFront()	value or undefined	the first value	O(1)
peekBack()	value or undefined	the last value	O(1)
at(index)	value or undefined	random access from the nearer end; negative counts from back	O(n/c)
pushFront(value)	this	add a value at the front	O(1)
unshift(value)	this	an alias for pushFront(value)	O(1)
addFront(value)	this	an alias for pushFront(value)	O(1)
pushBack(value)	this	add a value at the back	O(1)
push(value)	this	an alias for pushBack(value)	O(1)
add(value)	this	an alias for pushBack(value)	O(1)
addBack(value)	this	an alias for pushBack(value)	O(1)
popFront()	value or undefined	remove and return the first value	O(1)
shift()	value or undefined	an alias for popFront()	O(1)
removeFront()	value or undefined	an alias for popFront()	O(1)
popBack()	value or undefined	remove and return the last value	O(1)
pop()	value or undefined	an alias for popBack()	O(1)
removeBack()	value or undefined	an alias for popBack()	O(1)
pushValuesFront(values)	this	add values at the front (they end up reversed)	O(k)
pushValuesBack(values)	this	add values at the back	O(k)
clear()	this	remove all values	O(1)
[Symbol.iterator]()	iterator	return the default iterator starting from the first value	O(1)
getReverseIterator()	iterator	return the reverse iterator starting from the last value	O(1)

Static members:

Member	Return type	Description	O
from(values, options)	UnrolledList	create a list from an iterable	O(k)

Notes on properties and methods

Front/back operations and iteration only — this is the pipeline container. It deliberately has no mid-sequence surgery, no pointers, and no node identity: for those use the regular lists; for bounded keep-last-N semantics use RingBuffer.

Chunks are mini two-ended arrays: values fill from the appropriate end and never move afterwards. Popped slots are cleared, so drained chunks never pin dead references. A chunk opened by pushFront fills front-down and one opened by pushBack fills back-up, so alternating end-pushes can leave chunks partially filled — the classic unrolled-list trade, bounded by one chunk per end.

Where it sits (measured on bench/bench-unrolled.js, 2026-07-18, fill 10k + iterate + drain): UnrolledList 253μs vs ValueList 668μs (~2.6×) and Array 640μs (shift hurts it); RingBuffer 205μs stays the outright throughput champion. Choose the unrolled list when the pipeline is unbounded and spiky — a ring buffer doubles-and-copies on growth, while unrolled growth is incremental (one chunk at a time) with no copying, giving flatter latency; choose the ring when capacity is known or growth spikes are acceptable.

Exports

UnrolledList is the default export and is also exported by name.