I see. As it is impossible to overlook 🤪😎 And I’m aware of how important they are. Best regards, Karl.

> And I’m aware of how important they are

Actually, linked lists have recently become completely unimportant! :) ... due to the mind-bogglingly high cost of cache misses on modern memory architectures. Linked lists tend to maximize cache misses, at least compared to the much more compact vectors.

This is analysed in more detail in The 10**21 Problem (Part 3) where Stroustrup noted that on modern memory architectures, C++ linked lists are typically 50 to 100 times slower than vectors.

Update: Much later I remembered Re: Data structures in Perl. A C programmer's perspective. (vector vs linked list performance).

> Actually, linked lists have recently become completely unimportant!

For how long?

Things which were relevant in the 90s became unimportant because of hardware a dozen years later to reappear as relevant after the same time span again.

Example:

• Multiplication on the Motorola 68000 was so slow (~74 cycles IIRC) that Mandelbrot sets were best implemented by precalculating a big lookup table in RAM (~8 cycles)
• Later using lookup tables became obsolete by the speed difference between CPU calculations compared to RAM access.
• Later caches became so big that big tables could fit again easily

Lessons:

• Efficiency of algorithms are effected by hardware
• You can't always predict how hardware evolves.

All this doesn't justify not to study linked lists:

• they can be used in many contexts
• with many advantages
• are easily implemented (see LISP)
• and performance is not always an issue.
Now what exactly do you mean with a vector?

If you mean something with equidistant entries, 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?

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

I think that Stroustrup's concept as referenced, is completely out of context. Searching a "short" array or traversing a "short" linked list sequentially will always be relevant! A vector to a short linked list (like a hash table) is very efficient.