I wholeheartedly agree that many—if not most—algorithms classes don’t sufficiently talk about the limitations of the models used and how to handle this. I’m a big fan of Algorithm Engineering, which is best imagined as a cycle of design, analysis, implementation and experiments, with each stage influencing the next. This has led to some exceptional results (e.g. the route planning algorithms used by Google/Bing/Apple Maps, which are around 5 orders of magnitude faster than Dijkstra’s algorithm by using clever pre-processing that exploits the structure of road networks. Their asymptotic query complexity on general graphs is still the same as Dijkstra’s, iirc)

Nitpick, but your list-based LRU cache’s operations wouldn’t be in o(1) but rather O(1) – little oh means strictly slower growth, in this case sub-constant. Probably just a typo though. And it could be further optimised for locality by using a cyclic buffer instead of a linked list (-> no pointer chasing + sequential access), but see kilburn’s answer (the structure in the paper solves a different problem)