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

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.

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.
• LeftistHeap — a merge-based leftist heap. See Wiki's Leftist tree for more details.
• SkewHeap — a merge-based skew heap. See Wiki's Skew heap for more details.

Queue and Stack

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.

Trees

• SplayTree — a splay tree. See Wiki's Splay tree 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/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/leftist-heap.js — the LeftistHeap 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.
• Trees:
  • tree/splay-tree.js — the SplayTree 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.
• 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.
  • LeftistHeap — the merge-based leftist heap class.
  • SkewHeap — the merge-based skew heap class.
• Queues:
  • Queue — the queue adapter class.
• Stacks:
  • Stack — the stack adapter class.
• Trees:
  • SplayTree — the splay tree class.
  • SplayTreeNode — the splay tree node class.