> 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 g

> 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.