Home

list-toolkit

A toolkit for lists, related data structures, and their practical applications.

Search

🔍 Search this wiki — ranked, deep-linked search via wiki-search; install the bookmarklet to search in place. Fallback: GitHub wiki search.

Concepts

Lists are simple yet versatile, with many possible design trade-offs. Suggested reading order:

• Backgrounder — general concepts, their analysis and design decisions. A must read!
  • Improving SLL — a visual representation of lists operations and analysis of ways to solve the potential problems.
• Choosing a data structure — when to reach for each structure, what it buys, and how it differs from its alternatives.
• API conventions — toolkit-wide naming rules: getters vs getXXX() methods, size/length, what push/pop mean per family, and the documented exceptions.
• Concepts: list API — a conceptual API for singly and doubly linked lists. A must read!
• Concepts: pointers — a concept of pointers to list nodes and why they are needed.
• Concepts: ranges — a concept of node ranges.
• Concepts: external list API — external (headless) lists and their uses.
• Concepts: value list API — value lists.

DLL: doubly linked lists

The most flexible variant. API reference:

• Foundation — the foundational classes and methods of the implementation.
• Lists — the hosted list classes and methods.
• Pointers — the pointers API for doubly-linked lists.
• External lists — the external headless lists API.

SLL: singly linked lists

Minimalist and most performant. API reference:

• Foundation — the foundational classes and methods of the implementation.
• Lists — the hosted list classes and methods.
• Pointers — the pointers API for singly-linked lists.
• External lists — the external headless lists API.

Unrolled list

• UnrolledList — a chunked value list for bulk pipelines: one allocation per chunk, contiguous iteration, no growth copies. See Wiki's Unrolled linked list for more details.

List utilities

• List utilities — helpful utilities for working with lists.
• NT list utilities — utilities for working with null-terminated lists.

Caches

List-based caches with various eviction policies:

• CacheLRU — a least recently used (LRU) cache.
• CacheFIFO — a first in, first out (FIFO) cache.
• CacheLFU — a least frequently used (LFU) cache.
• CacheRandom — a cache with randomly removed items.
• CacheSLRU — a segmented LRU (scan-resistant) cache.
• CacheClock — a CLOCK (second chance) cache.

All caches share the same API but may have different options. See Caches.

Also provides a cache decorator for function/method results keyed by the first argument.

Heaps

Efficient min/max tracking:

• MinHeap — an array-based min-heap. See Wiki's Heap for more details.
• IndexedHeap — an array-based min-heap with intrusive element indices: O(1) membership, O(log n) update/remove by handle (decrease-key).
• LeftistHeap — a merge-based leftist heap. See Wiki's Leftist tree for more details.
• PairingHeap — a merge-based pairing heap: O(1) push/merge, decrease-key by node handle. See Wiki's Pairing heap for more details.
• SkewHeap — a merge-based skew heap. See Wiki's Skew heap for more details.

Queue, Stack, and Deque

List-backed adapters:

• Queue — a FIFO queue adapter. See Wiki's Queue for more details.
• Stack — a LIFO stack adapter. See Wiki's Stack for more details.
• Deque — a double-ended queue adapter with rotate(). See Wiki's Deque for more details.
• RingBuffer — an array-backed deque on a circular buffer: contiguous, allocation-free at steady state, optional keep-last-N bounded mode. See Wiki's Circular buffer for more details.

Trees

• SplayTree — a splay tree. See Wiki's Splay tree for more details.

Skip list

• SkipList — a probabilistic ordered container with expected O(log n) operations and range scans. See Wiki's Skip list for more details.

Timer wheel

• TimerWheel — a hashed timing wheel: O(1) schedule/cancel/reschedule, logical-time ticks. See Wiki's Timing wheel for more details.

Free list

• FreeList — an intrusive object pool for recycling nodes (GC-pressure control). See Wiki's Free list for more details.

Release history

• Release notes — per-version release notes (canonical long-form; the README carries a cliff-notes summary).

Direct links

Direct links to files

• Caches:
  • cache.js — the main user-facing module.
  • cache/cache-lru.js — the LRU cache.
  • cache/cache-fifo.js — the FIFO cache.
  • cache/cache-lfu.js — the LFU cache.
  • cache/cache-random.js — the random cache.
  • cache/cache-slru.js — the segmented LRU cache.
  • cache/cache-clock.js — the CLOCK cache.
  • cache/decorator.js — the cache decorator.
• DLL:
  • list/nodes.js — the foundational module that provides base classes.
  • Hosted node-based DLL:
    • list.js — the main user-facing module for doubly linked lists.
    • list/core.js — the implementation.
  • Hosted value-based DLL:
    • value-list.js — the main user-facing module.
    • list/value.js — the implementation.
  • External headless node-based DLL:
    • ext-list.js — the main user-facing module.
    • list/ext.js — the implementation.
  • External headless value-based DLL:
    • ext-value-list.js — the main user-facing module.
    • list/ext-value.js — the implementation.
  • list/ptr.js — the pointer module used by hosted DLL.
• SLL:
  • slist/nodes.js — the foundational module that provides base classes.
  • Hosted node-based SLL:
    • slist.js — the main user-facing module for singly linked lists.
    • slist/core.js — the implementation.
  • Hosted value-based SLL:
    • value-slist.js — the main user-facing module.
    • slist/value.js — the implementation.
  • External headless node-based SLL:
    • ext-slist.js — the main user-facing module.
    • slist/ext.js — the implementation.
  • External headless value-based SLL:
    • ext-value-slist.js — the main user-facing module.
    • slist/ext-value.js — the implementation.
  • slist/ptr.js — the pointer module used by hosted SLL.
• Heaps:
  • heap.js — the main user-facing module for heaps.
  • heap/min-heap.js — the MinHeap implementation.
  • heap/indexed-heap.js — the IndexedHeap implementation.
  • heap/leftist-heap.js — the LeftistHeap implementation.
  • heap/pairing-heap.js — the PairingHeap implementation.
  • heap/skew-heap.js — the SkewHeap implementation.
• Queue:
  • queue.js — the main user-facing module for queues.
• Stack:
  • stack.js — the main user-facing module for stacks.
• Deque:
  • deque.js — the main user-facing module for deques.
• Ring buffer:
  • ring-buffer.js — the main user-facing module for ring buffers.
• Trees:
  • tree/splay-tree.js — the SplayTree implementation.
• Skip lists:
  • skip-list.js — the SkipList implementation.
• Timer wheels:
  • timer-wheel.js — the TimerWheel implementation.
• Free lists:
  • free-list.js — the FreeList implementation.
• Unrolled lists:
  • unrolled-list.js — the UnrolledList implementation.
• Utilities:
  • list-utils.js — list utility functions.
  • nt-utils.js — null-terminated list utilities.

Direct links to classes

• Caches:
  • CacheLRU — the LRU cache.
  • CacheFIFO — the FIFO cache.
  • CacheLFU — the LFU cache.
  • CacheRandom — the random cache.
  • CacheSLRU — the segmented LRU cache.
  • CacheClock — the CLOCK cache.
• DLL:
  • Node — the foundational node class.
  • HeadNode — the class used by hosted DLL as the head node.
  • ValueNode — the class used by value-based DLL as the value node.
  • PtrBase — the base class for DLL pointers.
  • ExtListBase — the base class for DLL external lists.
  • List — the list class that implements node-based DLL.
  • ValueList — the list class that implements value-based DLL.
  • ExtList — the list class that implements an external headless node-based DLL.
  • ExtValueList — the list class that implements an external headless value-based DLL.
  • Ptr — the pointer class used by hosted DLL.
• SLL:
  • Node — the foundational node class.
  • HeadNode — the class used by hosted SLL as the head node.
  • ValueNode — the class used by value-based SLL as the value node.
  • PtrBase — the base class for SLL pointers.
  • ExtListBase — the base class for SLL external lists.
  • SList — the list class that implements node-based SLL.
  • ValueSList — the list class that implements value-based SLL.
  • ExtSList — the list class that implements an external headless node-based SLL.
  • ExtValueSList — the list class that implements an external headless value-based SLL.
  • Ptr — the pointer class used by hosted SLL.
• Heaps:
  • MinHeap — the array-based min heap class.
  • IndexedHeap — the indexed min heap class.
  • LeftistHeap — the merge-based leftist heap class.
  • PairingHeap — the merge-based pairing heap class.
  • SkewHeap — the merge-based skew heap class.
• Queues:
  • Queue — the queue adapter class.
• Stacks:
  • Stack — the stack adapter class.
• Deques:
  • Deque — the deque adapter class.
  • RingBuffer — the array-backed deque class.
• Trees:
  • SplayTree — the splay tree class.
  • SplayTreeNode — the splay tree node class.
• Skip lists:
  • SkipList — the skip list class.
  • SkipListNode — the skip list node class.
• Timer wheels:
  • TimerWheel — the hashed timing wheel class.
• Free lists:
  • FreeList — the object pool class.
• Unrolled lists:
  • UnrolledList — the chunked value list class.