Comparisons
Two things routinely conflated, put side by side. Neither column is the winner — what decides is the workload and the machine.
ISA vs MicroarchitectureArray traversal vs Linked-list traversalLatency vs BandwidthCPU vs GPUCPU cache vs OS page cacheHardware thread vs OS threadPolling vs InterruptsBranch vs Branchless
Array traversal vs Linked-list traversal
Both O(n). The array wins by a wide margin because contiguity turns one miss into sixteen hits and lets the prefetcher run ahead; the list pays a dependent miss per node and can never overlap them.
Array traversalOpen lesson →
Strengths
Contiguous, prefetchable, one miss amortized over a whole line
Costs
Insertion in the middle moves elements; growth reallocates
Use when
You iterate more than you restructure — which is most of the time
Linked-list traversalOpen lesson →
Strengths
O(1) insertion given a node, and stable addresses
Costs
A dependent cache miss per node, and no spatial locality at all
Use when
You restructure constantly and rarely traverse, or nodes are large and stable
| Dimension | Array traversal | Linked-list traversal |
|---|---|---|
| Complexity of traversal | O(n) | O(n) |
| Misses per element | One per line | Up to one per element |
| Prefetcher can help | Yes | No — the address is not known yet |
| Misses can overlap | Yes | No — each depends on the last |