One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?
When the use case requires insertion/removal from the middle of the list. An LRU cache is about the most common use case I've run across. (The "LRU" part requires it to often bump an item to the end of the list, so LL's excel here, as we can shift the element's position in the list in O(1) time. An LRU structure would normally pair the LL with a HashMap, which maps the cached item to its LL entry, so that we've also got a O(1) search into the LL, and don't hit the problem in the article.)
> yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations.
I see them employed very, very rarely. Vectors¹ are by far more common in every codebase I've ever worked on. (And should be one's default, IMO, if all you need is a container of stuff that you're going to iterate over, which is the usual case, for the reasons in the article.)
¹ignoring cases where a hash(map|set) is required; then our codebase uses that, b/c that's what's needed.
std::deque will invalidate iterators in some cases. Since my example above was an LRU cache, the cache's removal of an item from the middle of the list (to shift it to the end) is one of those actions that would invalidate iterators in a std::deque.
(Not to malign std::deque: it is a useful datastructure in its own right, and if you need queue-like semantics (e.g. cheap remove from front), it's a better choice than a LL, and both are better than vectors for that purpose. I find deque's internals to be a bit weird … my goto would normally be a ringbuffer, but the STL provides deque instead, so eh, it's good enough, if a bit odd IMO.)
Yes, and constant time insertions/deletions in the middle of the list, assuming you know the address ahead of time.
This makes them great as backing queues in an LRU cache: given some key/value pairs, have a linked list whose nodes map to each key. Additions to the K/V store gets appended to the LL. This lets you easily remove the oldest n elements in the K/V store, by traversing from the head of the LL. It also lets you efficiently remove arbitrary elements from the K/V store, if you store the addresses of each LL node as values in the K/V, since deletions in the middle of the LL are constant time.
>yet I see them employed in various places all the time
I agree, however, that most LL applications (like the one I just mentioned) are fairly niche. LLs are overused because they’re dead simple to implement and commonly taught in intro CS classes.
They're also more useful on microcontrollers where there's no cache, no prefetcher, etc. Less code needed for the data structure means more free space for business logic, and there's no performance penalty for bad cache locality on a system without any cache. Also a hash table has to hash each input, which is a significant amount of work for many microcontrollers.
ListNode* a = new ListNode('A');
ListNode* b = new ListNode('B');
ListNode* c = new ListNode('C');
a.next = b;
b.next = c;
This is a linked list with the same shape as the list above, but with completely different performance characteristics:
int* data = new int[3];
data[0] = 'A';
data[1] = 'B';
data[2] = 'C';
int* links = new int[3];
links[0] = 1;
links[1] = 2;
links[2] = -1;
It depends on the use case.
If you're doing a lot of navigating over links before you reach the destination, maybe you want them separate. Could also be the data is large, even maybe stored on disk while the links are in memory, or whatever. There's a thousand different scenarios with different optimal arrangements.
It also allows you to keep multiple different lists to the same data, say sorted by different fields in the struct.
Sounds a lot like “draw the rest of the damn owl.” [0] :-)
DBMSs and file systems use (extremely sophisticated) tree structures under the hood. Not sure that “linked lists are useful if the linking topology is much more complicated than a simple line” is a ringing endorsement of them.
( Here's an enjoyably lucid explanation on how to draw such an owl: https://www.youtube.com/watch?v=aZjYr87r1b8 )
You actually don't. You can just keep two lists within the same structure, one for occupied nodes and one for free nodes, and just move deletions to the head of the free nodes list.
Example List:
Data: [ a, 0, c, d, e ]
Links: [ 2, -1, 3, 4, -1 ]
Head of occupied nodes: 0
Head of free nodes: 1
Occupied Nodes: 0 -> 2 -> 3 -> 4 -> []
Free Nodes: 1 -> []
data[2] = empty // free data
links[2] = 1 // Repoint 2 -> 1
links[0] = 3 // Repoint 0 -> 3
firstFreeNode = 1
Data: [ a, 0, 0, d, e ]
Links: [ 3, 2, -1, 4, -1 ]
Head of occupied nodes: 0
Head of free nodes: 2
Occupied Nodes: 0 -> 3 -> 4 -> []
Free Nodes: 2 -> 1 -> []This also technically applies to lockless data structures for some high performance code too. But those tend to be much much more tightly tuned for performance and the specific CPU they are intended to run on.
only pertains to languages like C. In a virtual machine language like java, this isn't a property that can exist (there's no such thing as an address - at least as far as the language is concerned).
Vectors and arrays have the problem of needing contiguous memory. If an inner cell can have different size, or worse change it mid work, things get ugly really fast.
Your question is more accurate than you realize! Because the answer is... the past.
Up until about the 486/50MHz era, CPUs and memory were attached to each other; one CPU cycle was approximately equal to one memory access. I don't mean that you could reach out to RAM in exactly one cycle and get a value, there were still some CPU caches and other considerations, but it was much closer to that ideal than on modern systems. And if you go back in time even farther, that actually was the case (Commodore 64, for instance).
(I don't know if there was ever a "true" 486/66 system, but I remember that as the CPU/clock speed where the CPU finally and definitively detached from RAM speed because that was generally a double-clocked 486/33 from the RAM's perspective. I can't quite remember the marketing term that was used. It's a dead term now because everything works that way.)
In those circumstances, traversing a linked list was not necessarily that much more expensive than a vector, and you could win on the other things a linked list can do faster than a vector, like insert in the middle, especially an insert in the middle when you were traversing the list anyhow. You could also win on a linked list containing a relatively large value organized just by pointers; a sort on the linked list manipulating just the pointers could win versus a sort that was trying to move around larger values constantly during the sort. And so on.
When memory accesses aren't hundreds and hundreds of CPU cycles, when your hardware doesn't have prefecting implemented, when your pointers aren't 64bits wide, when you aren't on modern systems essentially designed to make vector-based access go zoom, linked lists make a lot more sense.
This is how they got embedded in curricula so hard that they are taught to this day. They used to be a very important data structure. Now they're an antipattern. It happened gradually, though, and it doesn't help that linked lists are just about the easiest non-trivial data structure to teach and I'm not sure they could get removed from the standard curriculum for that reason alone.
"One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?"
Another problem linked lists have is that if you know that's what you're going to do, you can build vector-based solutions to that problem that work just fine. Vector-based stacks, for instance, are trivial, and O(1)-amortized for push and pop, which is good enough in practice. (A bit more care is needed than an only-growing vector but IIRC it can be done.) You need not just something linked lists are better at, but some bizarre cocktail of all the things they're just barely better at, and you still need to construct a win out of the combo. It's nearly impossible. Not quite impossible. I assume without looking that the Linux kernel still has some linked lists for good reason, as I'm sure if they could win on performance by removing them they would. But very hard.
Every pop moves the whole list unless you get fancy an implement it as an array with head and tail pointers and grow logic.
If you keep a tail pointer inserts are likewise O(1).
You rarely traverse them.
(The best optimization you could do in such a case would be to allocate multiple slots per pointer, to amortize the malloc/free time. Then you'd want to run benchmarks to tell what the optimal amount of slots would be. If a vector is optimal, as I strongly expect it would be, the answer would come out to be, "all of them".)
Modern processors move chunks of RAM around really quickly. They're really optimized for it. It is one of the major things I'm referring to when I say our systems have been optimized for C. I often wonder about what an architecture designed in a world where linked lists were dominant would look like. However, it is certainly not this world.
The term I remember was 486DX2-66 , so was it DX2?
Inserting an element in middle is probably only legit use but it is kinda rare to have large enough data that you frequently insert in mid