When people talk about linked lists “storing data all over the place,” what they are really concerned about is locality of reference, i.e. minimizing the probability of a virtual-memory page fault ... which involves stopping the process in its tracks, doing a physical I/O to retrieve the page from a spinning disk, then restarting the process where it left off. If you only do that “occasionally,” as the operating-system strives to enable you to do, then all is well. But if the number of page faults becomes, and stays, excessive, then the system is “thrashing.” (The shape of the throughput-curve in a thrash situation is elbow-shaped: beyond the thrash point, performance for pretty much the entire system degrades exponentially. As they put it in the movie Ghostbusters, the result is “real Wrath of God stuff.”)
I will admit that I really don’t know how Perl stores a vector, or for that matter, a list or a hash. Concerns about cache-line misses are beyond my control since they are wholly dependent upon the particular hardware upon which my software might find itself running. But locality-of-reference is something that I can readily keep in mind, as being something that will very-directly affect the execution of my code far more than the low-level perlguts of Perl’s very highly optimized implementation.
You can build any sort of data-structure you may require in Perl, or, more likely, discover that CPAN has already done it for you. Red-black trees? Sure: Tree::RedBlack or Tree:RB, to name two.
Nearly all of the time, when I stumble upon a failed-program, the manifest symptom of the problem is either a timing-hole or (more likely), thrashing. The solution is to choose a different algorithm to solve the problem. By the time I first see it, the code has been “diddled” to the point that it is frankly no longer even readable, and nothing helped.