3 ms·

> Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bri

> Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). I think you're overcorrecting here. There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Today, in many cases, arrays are faster. And that awareness of caching effects is becoming greater. But I think there's a tendency to over-apply new knowledge that seems counter-intuitive. The reality is somewhere in the middle. Arrays can be surprisingly fast, even when you need to shift stuff around to insert or copy to grow. But there are still plenty of cases where linked lists are better if you are doing a lot of inserting or rearranging. I don't think the guidance is so much "linked lists bad!" as it is "arrays maybe not bad".

lmilcin 5y ago
> There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Nothing to do with caches or conventional wisdom no longer being true. Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert? Unless you have some kind of index to the list (in which case it no longer is a linked list, it is some other data structure), you have three options: a) at the beginning of the list b) at the end of the list c) in the middle of the list, in which case you need to run linear search to find the place. If you want to do this at the end of the list, then array list has the same amortized cost as linked list. If you need to do this at the beginning of the list, then array list can be reversed. Unless you have the very special case of having to add at both beginning and end of the list. So most likely you need to insert somewhere within the list to see the improvement over an array list. But then you need to do the linear search and the search is so much slower with linked list that it completely offsets the cost of copying of all that data.
- munificent 5y ago
  > Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert? You usually have a pointer to the node where you want to insert. I don't think many people would suggest using linked lists in cases where you actually do need to seek for the insertion point.
- deleted 5y ago
  [deleted]

lmilcin 5y ago

> There used to be a conventional wisdom that linked lists were always faster than dynamic arrays because you don't have to copy or shift items. But then CPUs got faster while memory didn't and caching effects became so prevalent that that conventional wisdom is no longer true. Nothing to do with caches or conventional wisdom no longer being true. Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert? Unless you have some kind of index to the list (in which case it no longer is a linked list, it is some other data structure), you have three options: a) at the beginning of the list b) at the end of the list c) in the middle of the list, in which case you need to run linear search to find the place. If you want to do this at the end of the list, then array list has the same amortized cost as linked list. If you need to do this at the beginning of the list, then array list can be reversed. Unless you have the very special case of having to add at both beginning and end of the list. So most likely you need to insert somewhere within the list to see the improvement over an array list. But then you need to do the linear search and the search is so much slower with linked list that it completely offsets the cost of copying of all that data.

munificent 5y ago
> Think for a second, if you want to insert somewhere inside your shiny linked list, how do you find where to insert? You usually have a pointer to the node where you want to insert. I don't think many people would suggest using linked lists in cases where you actually do need to seek for the insertion point.
deleted 5y ago
[deleted]