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: double 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 more complex decorator.

Heaps

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

• MinHeap — a min-heap. See Wiki's 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

Queue is a classic data structure. See Wiki's Queue for more details. The toolkit provides the following queue:

• Queue — an adapter for lists.

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 implementation.
• Queue:
  • queue.js — the main user-facing module for queues.

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 min heap class.
• Queues:
  • Queue — the queue adapter class.