Unrolled linked list
From Wikipedia, the free encyclopedia

In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references. It is related to the skip list and the B-tree.

Overview
A typical unrolled linked list node looks like this:

record node {
node next // reference to next node in list
int numElements // number of elements in this node, up to maxElements
array elements // an array of numElements elements, with space allocated for maxElements elements
}

Each node holds up to a certain maximum number of elements, typically just large enough so that the node fills a single cache line or a small multiple thereof. A position in the list is indicated by both a reference to the node and a position in the elements array. It's also possible to include a previous pointer for an unrolled doubly-linked linked list.

To insert a new element, we simply find the node the element should be in and insert the element into the elements array, incrementing numElements. If the array is already full, we first insert a new node either preceding or following the current one and move half of the elements in the current node into it.

To remove an element, similarly, we simply find the node it is in and delete it from the elements array, decrementing numElements. If numElements falls below maxElements ÷ 2 then we pull elements from adjacent nodes to fill it back up to this level. If both adjacent nodes are too low, we combine it with one adjacent node and then move some values into the other. This is necessary to avoid wasting space.

Performance

One of the primary benefits of unrolled linked lists is decreased storage requirements. All nodes (except at most one) are at least half-full. If many random inserts and deletes are done, the average node will be about three-quarters full, and if inserts and deletes are only done at the beginning and end, almost all nodes will be full.

Another advantage of unrolled linked lists is that they perform a number of operations, typically associated with arrays, much more quickly than ordinary linked lists. For example, when indexing into unrolled linked list, we can progress a node at a time rather than an element at a time, reducing the indexing time to O(n/m) instead of O(n).

Unrolled linked lists also perform sequential traversal much more rapidly, due to their cache behavior: iterating through an ordinary linked list of n elements triggers n cache misses in the worst case, and about 2nv/m in the best case, assuming v and s are about the same size. Iterating through an unrolled linked list of n elements triggers only 2n/m cache misses in the worst case and n/m in the best. Even arrays can do little better than this best case, with about n/(m+v/s) misses. When v is about s, linked lists have twice as many cache misses as unrolled linked lists in the best case, and m/2 times as many in the worst case, which in practice can speed up list traversal by as much as 10 times or more.