A Cache-conscious structure definition for list

A list data structure is a collection of nodes accessible one after another beginning at the head and ending at the tail. The standard way to implement a linked list is to have each node of the list contain both its value and a pointer indicating the location of the next node in the list. However, such design is not suitable for traversal since accessing its loosely distributed nodes may trigger frequent cache replacements. This study presents a novel structure definition for list, the principle of which is to extract the frequent-accessed elements from each node and store them in contiguous memory space. Besides, adjust the layout of contiguous memory space to match the data access type of traversal. With the help of the modified data distribution, a cache miss will load not only the data required for traversing to current node but also the data required for traversing to next nodes and thus reduce the number of cache misses as well as the required cache resource. The experimental results show that, compared with the standard list design, the traversal efficiency is improved significantly.