It's funny that algo folks still like to talk about linked lists. But these days we avoid them like the plague because they thrash caches and prefetchers.
In the 16-bit era, we didn't have either of ...
@nprofile1q... Well, yes but also no. I use them all the time for “cold” lists that get iterated once or rarely, or advance one item and then wait.
You can also mitigate a lot of that sticking the nodes in a fairly compact array and linking them with indexes. I think it was @nprofile1q... that recently pointed out you can even just iterate those in array order in many cases when you don’t care about ordering. (Ex: need to increment every item in an otherwise ordered list)
You can also mitigate a lot of that sticking the nodes in a fairly compact array and linking them with indexes. I think it was @nprofile1q... that recently pointed out you can even just iterate those in array order in many cases when you don’t care about ordering. (Ex: need to increment every item in an otherwise ordered list)
1
