Unrolled linked list

It can dramatically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references.

It is also possible to include a previous pointer for an unrolled doubly linked list.

One of the primary benefits of unrolled linked lists is decreased storage requirements.

space, although v may be smaller, and arrays, one of the most compact data structures, require

If the elements are particularly small, such as bits, the overhead can be as much as 64 times larger than the data on many machines.

Additionally, if the size of each element is small compared to the cache line size, the list can be traversed in order with fewer cache misses than ordinary linked lists.

In either case, operation time still increases linearly with the size of the list.