Sorry LanX, I confess I was indulging in the traditional Aussie pastime of stirring when I claimed that linked lists have become completely unimportant. :) You've made some excellent valid points in defence of linked lists. To answer your last question more seriously:

How would you implement an array of strings of varying length without links? And how are these string-links less likely to cause cache misses?

I'd try using the standard library: std::vector<std::string> ... hoping/trusting/assuming that this common case has already been optimized ... and googling indicates that most implementations of the C++ standard library do in fact use some form of Short/Small String Optimization (SSO) so that smallish strings are not stored on the heap, vastly improving locality of reference:

A std::string typically stores the string as a pointer to the free store ("the heap"), which gives similar performance characteristics as if you were to call new char [size]. This prevents a stack overflow for very large strings, but it can be slower, especially with copy operations. As an optimization, many implementations of std::string create a small automatic array, something like char [20]. If you have a string that is 20 characters or smaller (given this example, the actual size varies), it stores it directly in that array. This avoids the need to call new at all, which speeds things up a bit...

If I get time later, I may try to do some sort of benchmark of your interesting use case in both Perl and C++.