The true cost of linked lists
Big-O notation relies on several simplifying assumptions which are wrong in practice. It's not useless, but it's for analyzing algorithmic complexity, not for analyzing algorithmic performance.<p>Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others.<p>Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.<p>Etc, etc. An algorithm's complexity is loosely correlated with its performance, but the two are not identical.