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/getter 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