Don’t blindly prefer emplace_back to push_back

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.

Even if linked lists and double linked lists aren't all that universally useful by themselves, they teach all the basics about taversing data structures by references / pointers that more complex trees and graphs require. A linked list is just a degenerate tree with at most one child for each parent. So I think teaching that isn't a bad decision.

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.

I couldn't have said it better :)

They're also an example of a data-structure which works pretty in a concurrent setting - you can get away with a single atomic reference for an unbounded FILO queue implemented with a linked list. Adding and removing items to it is then dirt-cheap - provided you don't go through the queue quickly and job running time > iteration time.

But with all things in computer science, it really depends on your use-case.

good point, they may still be useful as a pedagogical tool to introduce pointer-based structures.