Detailed linked list

An example of a detailed linked list.

An expanded linked list is a list , each physical element of which contains several logical elements (usually in the form of an array, which allows to speed up access to individual elements).

Allows you to significantly reduce memory consumption and increase performance compared to a regular list. Particularly large memory savings are achieved with a small size of logical elements and a large number of them - for example, a single-linked list of 10 thousand four-byte integers with four-byte memory addressing will take 40 thousand bytes for the actual value, plus 40 thousand bytes for addresses, totaling 80 thousand bytes; if we combine the numbers into 100 arrays of 100 elements each, the memory consumption for addresses will drop to 400 bytes, and the total consumption will be 40,400 bytes.

The performance gain is achieved due to the fact that most of the operations are performed on relatively small arrays, which are usually entirely placed in the cache . Thanks to this, the speed of the program can be even higher than when working with ordinary arrays. It is easy to add new elements to the expanded list - without having to rewrite the entire array, which is a big problem when working with regular arrays.

When implementing, you must carefully select the size of the "block" (the number of elements in arrays). If the block size is too large, the list begins to suffer from the same problems as an ordinary array: long insertion of elements at the beginning or middle, long removal of elements from the same, etc. If too small, the memory consumption increases.