List toolkit

Efficient list-based data structures for JavaScript. Pure ESM, zero dependencies, works in Node.js, Bun, Deno, and browsers.

Data structures included:

• Linked lists — doubly and singly linked, circular. Node-based (link properties on your objects) or value-based (wraps values in nodes). Hosted (sentinel head) or headless (external pointer).
• NT list converters — convert null-terminated lists to/from circular lists in place.
• Heaps — min heap, leftist heap, skew heap, pairing heap (O(1) push/merge, decrease-key by handle), indexed heap (O(1) membership, update/remove by handle).
• Caches — LRU, LFU, FIFO, random, segmented LRU (scan-resistant), CLOCK (second chance). Includes a decorator for functions, methods, and getters.
• Queue, Stack, and Deque — list-backed adapters; the deque adds O(1) both-end operations and rotate().
• Ring buffer — array-backed deque on a circular buffer: fastest raw throughput, O(1) random access, optional keep-last-N bounded mode.
• Unrolled list — chunked value list for bulk pipelines: one allocation per chunk, contiguous iteration, no growth copies.
• Splay tree — self-adjusting binary search tree.
• Skip list — probabilistic ordered container: expected O(log n) search/insert/remove, floor/ceil, ordered and range iteration.
• Timer wheel — hashed timing wheel: O(1) schedule/cancel/reschedule, logical-time ticks driven by your clock.
• Utilities — push/append values, find, remove, validate, node pooling (free list), and more.

Works with your existing linked lists — no wrapper objects required.

• Flexible, efficient, simple.
• Zero dependencies, no surprises.
• Pay only for what you use.
• Usable as a foundation for other data structures.

Read all about the implemented ideas in the Backgrounder, and pick the right tool with Choosing a data structure.

All lists share a consistent API: create from iterables, push/pop, insert/extract/remove, forward and reverse iterators, stable sort, sorted insert/merge, reverse, and customizable link names.

Full documentation is in the wiki — browse the index, or search it by name.

Installation

npm install list-toolkit

Introduction

See the wiki for full documentation. Quick examples below.

Value lists wrap arbitrary values:

import ValueList from 'list-toolkit/value-list.js';

const list = ValueList.from([1, 2, 3]);

// iterate over the list manually
for (let node = list.front; node !== list; node = node.next) {
  console.log(node.value); // 1, 2, 3
}

// iterate over the list with an iterator
for (const value of list) {
  console.log(value); // 1, 2, 3
}

// add more values:
list.pushBack(4);
list.pushFront(0);

console.log(list.popFront()); // 0
console.log(list.front.value); // 1

Lists can be made of arbitrary objects:

import List from 'list-toolkit/list.js';

class Person {
  constructor(name) {
    this.name = name;
  }
}

const john = new Person('John'),
  jane = new Person('Jane'),
  jim = new Person('Jim'),
  jill = new Person('Jill');

const people = List.from([john, jane, jim, jill]);

// iterate over the list manually:
for (let node = people.front; node !== people; node = node[people.nextName]) {
  console.log(node.name); // John, Jane, Jim, Jill
}
// yes, the link names are customizable, can be strings or symbols, for example:

const ladies = List.from([jane, jill], {nextName: 'n', prevName: 'p'});

// iterate over ladies
for (let node = ladies.front; node !== ladies; node = node.n) {
  console.log(node.name); // Jane, Jill
}

// let's move Jim to the front and John to the back:
people.moveToFront(jim);
people.moveToBack(john);

// sort the list
people.sort((a, b) => a.name.localeCompare(b.name) < 0);

for (const node of people) {
  console.log(node.name); // Jane, Jill, Jim, John
}

// let's extract all people from Jill to Jim
const ji = people.extractRange({from: jill, to: jim});
for (const node of people) console.log(node.name); // Jane, John
for (const node of ji) console.log(node.name); // Jill, Jim

// add them back:
people.append(ji);
for (const node of people.getReverseIterator()) {
  console.log(node.name); // Jim, Jill, John, Jane
}
ji.isEmpty === true;

// BTW, the list `ladies` is unchanged

License

BSD 3-Clause "New" or "Revised" License. See the LICENSE file for details.

Release History

• 2.4.1 Fixed a crash in meta-utils descriptor factories. Modernized iterator helpers.
• 2.4.0 Added skip lists, deques, ring buffers, timer wheels, indexed and pairing heaps, unrolled lists, object pools, SLRU and Clock caches. Splay tree order statistics, stable list sorting, exact LFU, faster heaps.
• 2.3.2 Updated dev dependencies.
• 2.3.1 Bugfixes. Improved TS typing tests. Updated docs. Updated dev dependencies.
• 2.3.0 Added TypeScript declarations for all modules. Added JSDoc. Removed CJS build. Bugfixes. Added missing methods.
• 2.2.6 Updated dev dependencies.
• 2.2.5 Updated dev dependencies.
• 2.2.4 Updated dev dependencies.
• 2.2.3 Updated dev dependencies.
• 2.2.2 Updated dev dependencies.
• 2.2.1 Technical release: updated deps, added more tests.
• 2.2.0 Added leftist and skew heaps.
• 2.1.1 Allowed functions to be used as nodes. Updated deps.
• 2.1.0 Added splay tree. Updated deps.
• 2.0.0 New major release.

For more info consult full release notes.