yyqux
Joined 13 years ago
Joined 13 years ago
Why is this surprising to anyone? I mean, bloody hell, anyone who's watched Law & Order should know that there are lawful procedures for these things.
I think the issue here is that, in the past, with shallower cache hierarchies, models that assumed a constant cost per memory access would maybe be off by smallish factor (I don't know, maybe 50%).
However, now memory access is frequently the limiting factor for an algorithm, and there can easily be an order of magnitude in variation between the average memory access latency for different algorithms (i.e. cache-smart versus cache-dumb).
In a lot of cases they really want to be able to do O(1) inserts/deletes at the beginning/end of the list, which is where linked lists do have a major advantage.
Short linked lists aren't too bad, using them for storing bulk data is mostly a bad idea unless you can't avoid it.
Sometimes they're the right data structure, but I've definitely come across programmers who want to use a linked list for everything, even in code where performance is important.
Edit: the general advice that you should avoid linked lists for performance reason is good. The idea that you should never use them I just took as additional trolling for page views.
I think the first is great when it comes to public understand of science, if you can do it well. The second is a bit problematic when people are left with a misleading impression of what they know.