Comment by rcxdude
2 days ago
Linked lists are cool but they are terrible for cache performance, so their apparently elegant performance characteristics are often illusory. And hybrid data structures which get you the best of both worlds are quite complicated to implement. I think that's why there's a general pressure against using them unless you have a very specific reason (and ideally some measurements) to demonstrate that they are a good option.
(part of this I think is some C teaching which tended to overemphasize linked lists because they are useful for teaching the concept of pointers, which gave a lot of people learning C the impression that it should be the default way to represent a list of objects, when it's far more the exception than the rule)
Yeah, I'd blame mainly 2 factors for the continued undue influence of linked lists
1. CS professors teach them. The Programme Lead for our CS course still teaches linked lists as the first data structure in the DSA course. Does this type exist? Sure. Is it a good idea? Almost never. But you wouldn't think so from its prominence in the course materials.
2. The Linux kernel uses a LOT of linked lists. Multi-core atomic operations on mutable data, a nightmare you will probably avoid in your software is necessary for the OS kernel and so it has linked lists. Linux is very famous, but your software is almost certainly not an operating system kernel.
> but your software is almost certainly not an operating system kernel.
In general yes, but right now I'm contributing to folk.computer, which is a multithreaded task scheduler/central DB (among other things not relevant to the topic at hand). The biggest use of atomics is during statement insertion and removal, by using RCU operations in the central trie.
One of our current performance drags is the interpreter we use is not threadsafe, so we have to serialize and deserialize objects as they move between threads. This contributes to about 30% of Folk's CPU usage. So I'm currently working on making a threadsafe interpreter by porting the Tcl interpreter we use (Jimtcl), and I'm learning all the fun things around atomic ordering and threaded data structures. So I'm definitely the audience for these data structures.
A linked list is the simplest possible linked structure and should definitely continue to be taught, but you could add another lesson and exercise to compare its performance with dynamic arrays.
Traversing a linked list is terrible for performance. But in cases like the cache you are only poping from the front, appending to the back or removing which are all quite fast and require little pointer chashing.
Cache cost of individual allocations can be an issue but that can also be mitigated with a good allocator and even without special care can be quite performant in many applications.
I agree the linked lists shouldn't be the first structure you reach to. But there are situations where they can perform very well.
Even Lisp got all major data structures relativity early on, building only on lists is mostly used for prototyping.