Editing Unrolled linked list (section)

==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. Assume that:
* ''m'' = <code>maxElements</code>, the maximum number of elements in each <code>elements</code> array;
* ''v'' = the overhead per node for references and element counts;
* ''s'' = the size of a single element.
Then, the space used for ''n'' elements varies between <math>(v/m + s)n</math> and <math>(2v/m + s)n</math>. For comparison, ordinary linked lists require <math>(v + s)n</math> space, although ''v'' may be smaller, and [[array data structure|array]]s, one of the most compact data structures, require <math>sn</math> space. Unrolled linked lists effectively spread the overhead ''v'' over a number of elements of the list. Thus, we see the most significant space gain when overhead is large, <code>maxElements</code> is large, or elements are small.

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. Moreover, many popular memory allocators will keep a small amount of metadata for each node allocated, increasing the effective overhead ''v''. Both of these make unrolled linked lists more attractive.

Because unrolled linked list nodes each store a count next to the ''next'' field, retrieving the ''k''th element of an unrolled linked list (indexing) can be done in ''n''/''m'' + 1 cache misses, up to a factor of ''m'' better than ordinary linked lists. 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.