search

rust-unofficial / too-many-lists

Learn Rust by writing Entirely Too Many linked lists
https://rust-unofficial.github.io/too-many-lists/
MIT License
3.16k stars 276 forks source link

A note on history #261

Open jlxip opened 1 year ago

jlxip commented 1 year ago

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 commented 10 months ago

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. :smile: