Home

list-toolkit

After implementing list-based structures countless times, I finally decided to write them down as an open source project.

The toolkit deals with lists, related data structures and their practical applications.

Concepts

A list is a simple yet versatile data structure with a lot of possible design decisions. I suggest to skim over the wiki in the following 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

A doubly linked list is the most flexible data structure. The API is described in the following documents:

• 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

A singly linked list is the minimalist data structure yet the most performant. The API is described in the following documents:

• 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

The toolkit provides the following list utilities:

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

Caches

Caches are data structures based on lists. The toolkit provides the following caches:

• 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 have the same API but may have different options. The API is described in this document: Caches.

Additionally it provides a decorator to cache results of a function/method call based on the first argument: Cache decorator.

If you want a more complex caching schema for your functions, you can easily create a more complex decorator.

Heaps

Heaps are data structures used to track min/max elements efficiently. The toolkit provides the following heaps:

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

Strictly speaking, heaps are tree-like data structures, which are not usually based on lists. But they are frequently used together, so we decided to provide them as well.

Queue and Stack

Queue and Stack are classic data structures. The toolkit provides adapters for lists:

• 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

The toolkit provides the following tree implementations:

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

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.

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.