←back to thread

178 points todsacerdoti | 1 comments | | HN request time: 0.205s | source
Show context
jokoon ◴[] No.26340841[source]
Thanks for the article, there should be a huge list of those type of classic C++ misconceptions/FAQ style.

One of my favorite is "you don't need a linked list".

Although I'm still genuinely interested when a linked list is best suited. I'm also curious why they were invented and why they're taught, maybe just for teaching purposes...

replies(12): >>26340881 #>>26340918 #>>26340936 #>>26341086 #>>26341090 #>>26341157 #>>26341167 #>>26341203 #>>26341240 #>>26341290 #>>26341787 #>>26347246 #
beaconstudios ◴[] No.26340918[source]
Naively, I would assume that LLs are best used for long lists which are typically traversed incrementally, like a FILO-only job queue. That wouldn't perform better than a static array of statically-sized objects, but it could be better for eg. a list of structs with flexible array members (ie, variable-sized structs).

They might be good for traversed lists with the possibility of partway insertion too, or performing insertion sort. Hell they might even be good for traversed lists in the general case, but I'm not a low level dev so I don't know without testing it.

Fun exercise though!

I'm guessing they're taught because they're taught, in that special inertial way that education propagates. Originally, I bet they were introduced when implementing your own data structures rather than pulling a library was normal industry practice.

Of course there is tons of value in knowing about data structures and their characteristics, but probably not in knowing how to implement LLs.

replies(3): >>26341133 #>>26341145 #>>26341155 #
1. dmurray ◴[] No.26341145[source]
Everyone would probably agree it's good to teach trees in a CS data structures class. Linked lists make a nice introduction to this: what is a linked list except a tree with max branching factor 1? So you teach LLs on day one, and introduce in the simplest useful way the idea of a recursive data structure.