A cache miss occurs when a requested memory location is not present in the relevant CPU cache. It matters because irregular memory access can make software slower even when its theoretical operation costs look favorable. section 1.1
Linked lists often have weaker spatial locality than arrays because their elements are not guaranteed to occupy contiguous memory. After fetching one cache line, the next element may require another cache line, causing more cache misses. Unpredictable traversal also limits effective CPU prefetching and can prevent SIMD-based processing. section 1.1 section 1.1
Contiguous linked-list traversal
A benchmark compared iterating over an array with iterating over a linked list allocated contiguously. The linked-list iteration was still 230% slower: its assembly required more cycles per iteration, and its less predictable access pattern caused more cache misses and lower performance. section 1.1



