Memory: Why the Array Wins Even When the Step Count Says Otherwise
Big-O counts steps and assumes every step costs the same. It does not. A cache miss costs a hundred steps, and that is why a linked list loses to an array.
Problem Solving From Zero21