Comment by tialaramex
2 days ago
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.