Insert, Remove, and the Cost of Shifting
Post 9 of the Dynamic Arrays in C series · Full source code on GitHub The Price of Contiguous Memory Dynamic arrays earn their performance from a single property: contiguous memory. Every element sits next to its neighbor in a flat, uninterrupted buffer. The CPU’s cache prefetcher loves this, when you read element 0, elements 1 through 15 are already on their way into L1. Sequential iteration runs at memory bandwidth, not memory latency. This is why arrays outperform linked lists for traversal even though linked lists have O(1) insertion: the constant factor hidden inside big-O notation is dominated by cache behavior, and contiguous beats scattered by an order of magnitude on modern hardware. ...