VList: Described in “Fast Functional Lists, Hash-Lists, Deques and Variable
Length Arrays” by Phil Bagwell
(2002). Rosetta Code has a VList task
and Wikipedia had a VList
page, that has since been deleted. Racket has a VList
type.
Zig SegmentedList:
A stack data structure that allocates list segments sized in increasing powers
of two. Elements are never moved, so pointers to indices have the same
lifetime as the structure itself and elements do not need to be copyable. Most
elements are contiguous, making it cache-friendly. Append, pop, and index
operations are O(1). The container uses O(log n) storage for list segment
pointers.
Sparse set: Described in “An Efficient Representation for Sparse Sets” by Preston Briggs and Linda Torczon (1993) and popularized in “Using Uninitialized Memory for Fun and Profit” by Russ Cox (2008).
Go implementations:
Array-mapped trie: A trie with children indexed by a bitmap. Instead of a fixed-size array for its child branches, it has a dense array paired with a bitmap, where the population count below the bit index for the key indicates the array index for the value. It can be made persistent by cloning a node before modifying it.
Hash array-mapped trie: An array-mapped trie, where the key is a hash. This gives even key distribution and constant key length.
Flattened AST: A graph structure with child nodes referred to by index into an array arena, rather than directly. This makes value numbering easy.
GapVec:
A random access container (designed by me) with constant-time indexed removal
and an in-place free list. When an element is removed, its index is set to the
new head of the free list and its data is overwritten to be the index of the
old head of the free list.
XOR linked list: A doubly-linked list, where XOR of the previous and next pointers is stored and the pointers are recovered while iterating, giving it the space usage of a singly-linked list.
Skip list: An ordered list with O(log n) average complexity for search and for insertion. It is a tiered linked list, where each layer skips fewer elements.