In response to genuine hotspots, it can be a useful optimization at times to especially apply the third solution you proposed which creates a contiguous array of elements that are stored by value (ex: numbers, not variable-sized sub-sequences like strings), and more so if the resulting array doesn't need to store all the data of the original list (some fields might be irrelevant to subsequent usage).
For variable-sized subsequences it can be helpful sometimes too to transfer to a flat container, like
std::vector<char>, with null terminators to terminate one string from the next if the subsequent and repetitive access patterns are sequential. That might not be as helpful these days now that strings use SBOs, but there was a time long ago at least where that was enormously helpful in my cases that involved repetitive UTF8 string processing to just flatten it all out to one giant array of characters.
That said, the cases where I benefitted from such optimizations did not traverse the linked structure (tree in our case) 2 or 3 times. It was more like 100+ times a second with the original data in the linked structure not changing very frequently at all (not invalidating the data cached into a contiguous array), and on top of that it enabled us to do things like SIMD processing with the resulting array as we repeatedly looped through it.
One the biggest examples I can recall where that sort of optimization was useful was a motion hierarchy evaluation. To compute the resulting matrices of child matrices down a hierarchy, we had to traverse the motion hierarchy (tree) in breadth/level-first order to transfer motions from parent to child. There, it was very helpful to frame rates to just grab an array of elements out of that level-first traversal and use that array sequentially instead of traversing the tree over and over every single frame. In that case the motion of the items was dynamic and frequently changing, but not the structure of the tree (very infrequently changed). And we did only do that after seeing hotspots and cache misses there in VTune.
Also as pointed out linked structures don't necessarily have to result in a loss of spatial locality. You can even write linked lists using arrays where the array elements just store like a
next 32-bit index to skip to the next part of the array storing the next element, and use like
-1 in place of a
nullptr. Of course the
next index for element 40 might might skip to the 35,000th position in the array if you start inserting and removing all over the place in the middle of the list, but then you can restore the spatial locality with a simple copying pass which traverses the original list using those links and then inserts to the new list in order (in which case all neighboring nodes would be right next to each other in memory/array in the new copy). I often use that rep these days as I find it far less cumbersome than having to deal with separate allocators like free lists; in general I don't like to deal with memory allocator and data structure as two separate things to deal with in usage if I can help it.
Finally I could imagine even a case where traversing the list one time to copy to array only to traverse the array one time might be beneficial if the work done per iteration is hefty and capable of being done in parallel. The array, with its random access, allows that loop to be parallelized, whereas the linked list traversal is serial in nature.