A note on history

[jlxip]

First of all, I agree with everything that's said in the introduction. However, linked lists are terrible data structures is an incomplete argument. Same with linked lists are as niche and vague of a data structure as a trie.

There's a huge point that is not being taken into consideration about linked lists, one that I think would make the argument richer: history. All the points you noted are true for modern systems. Once I read The Art of Computer Programming, I came to realize that most slow and apparently bad algorithms and data structures are great under a specific set of assumptions. Linked lists were great at a time when the assumption CPU is slower than RAM was true, and cache wasn't a thing.

We teach every undergrad how to write a linked list. Yes, because most courses are outdated. At the time they were encouraged, they were truly the best.

[dharkness]

I learned about linked lists as a stepping stone to binary trees. IIRC, it was my first introduction to pointers and malloc as we'd only used static arrays at that point. Granted, this was in 1990. 😄