RingBuffer

Array-backed double-ended queue on a circular buffer — contiguous storage, O(1) operations at both ends, O(1) random access, and no allocation at steady state. Shares the Deque API, so the two are drop-in replacements for each other; measured ~5× faster than both a plain Array and the list-backed deque on steady-state queue churn.

Legend for tables

• API
  • options - an object with optional properties:
    • capacity - hard bound: pushing onto a full buffer evicts from the opposite end (keep-last-N semantics). Omit for an unbounded, growable buffer.
    • initialCapacity - initial slot allocation hint (default 16; rounded up to a power of two).
  • value - the value to be stored in the buffer
  • 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 trigger growth)
  • O(n) - linear time proportional to the buffer size
  • O(k) - linear time proportional to the argument size

ring-buffer.js

Implementation of RingBuffer:

import RingBuffer from 'list-toolkit/ring-buffer.js';

const queue = new RingBuffer();
queue.push(1).push(2).push(3);
console.log(queue.shift()); // 1 — Array-parity names, without Array.shift's O(n)

const lastFive = new RingBuffer({capacity: 5});
for (let i = 0; i < 100; ++i) lastFive.push(i);
console.log(Array.from(lastFive)); // [95, 96, 97, 98, 99]

Class RingBuffer

Methods:

Member	Return type	Description	O
constructor(options)	this	constructs a new RingBuffer	O(1)
isEmpty	boolean	checks if the buffer is empty	O(1)
isFull	boolean	true when a bounded buffer reached its capacity	O(1)
size	number	the buffer's size	O(1)
capacity	number	the hard bound, or Infinity when growable	O(1)
front	value or undefined	the first element	O(1)
back	value or undefined	the last element	O(1)
peekFront()	value or undefined	the first element	O(1)
peekBack()	value or undefined	the last element	O(1)
at(index)	value or undefined	random access; negative counts from the back (like Array#at)	O(1)
pushFront(value)	this	add an element at the front (evicts the back when bounded, full)	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 an element at the back (evicts the front when bounded, full)	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 element	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 element	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)
rotate(n = 1)	this	rotate: back → front for positive n (Python semantics)	see notes
clear()	this	remove all elements (keeps the allocation)	O(n)
[Symbol.iterator]()	iterator	return the default iterator starting from the first element	O(1)
getReverseIterator()	iterator	return the reverse iterator starting from the last element	O(1)

Static members:

Member	Return type	Description	O
from(values, options)	RingBuffer	create a ring buffer from an iterable	O(k)

Notes on properties and methods

Bounded mode ({capacity: N}): pushing onto a full buffer evicts the element at the opposite end — pushBack drops the front, pushFront drops the back. That makes a bounded ring the natural "keep the last N" sliding window (recent logs, rolling metrics).

rotate(n) follows Python's deque.rotate semantics. When the ring is physically full, rotation is just a head-index shift — O(1); otherwise it moves at most size / 2 elements.

RingBuffer vs Deque — same API, different trade: the ring is contiguous (cache-friendly, zero allocation at steady state, O(1) at()), the list-backed deque keeps stable node identity (references into the sequence survive any mutation) and never moves elements on growth. Measured on bench/bench-queues.js (2026-07-17): steady-state churn at 1k elements — RingBuffer 135μs vs Array 687μs and Deque 694μs per 10k push+shift pairs (~5×); fill+drain 10k — 229μs vs 626–688μs (~3×). Popped slots are cleared, so the ring never pins dead references. Growth transiently holds both the old and new backing arrays — O(n) peak auxiliary space during a doubling.

Exports

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