> When are linked lists actually good?

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.

This is exactly correct, since at least in C++, adding elements to any other data structure can invalidate the stored iterators/references in your hashmap. std::list will mean you pay a slight cost when adding new entries, which if your cache is working is hopefully not so often, or the malloc is already dominated by whatever is being cached.

In c++, std::deque is better than std::list as an address preserving backing store as it requires less memory allocations, less space overhead and objects will be closer together.

> std::deque is better than std::list as an address preserving backing store

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.)

(Cf. https://en.cppreference.com/w/cpp/container/deque)

>One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?

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.

Writing a system allocator (malloc).

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.

I think the problem is that we're thinking about linked lists like they are taught in intro to algorithms. Like

  ListNode* a = new ListNode('A');
  ListNode* b = new ListNode('B');
  ListNode* c = new ListNode('C');
  a.next = b;
  b.next = c;

That's a dumb way of implementing a linked list with no redeeming features outside of explaining the concept.

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;

With some elaboration (say exchange the arrays for a mmap-call, turn it into a tree instead of a list) and you're basically looking at the guts of a DMBS or a file system.

>turn it into a tree instead of a list

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.

[0] https://pbs.twimg.com/media/Bs13i6LCcAAvwCf.jpg

My point is that this general sketch of a layout with arrays of offset pointers roughly generalizes to something like a B or B+-tree fairly well, and that's a fairly simple data structure. You can absolutely implement a file system with passable performance with either of those tree structures.

( Here's an enjoyably lucid explanation on how to draw such an owl: https://www.youtube.com/watch?v=aZjYr87r1b8 )

This has the same issues as just using an array to store the data. If you remove a node in the list now you have to rewrite all the values in the links array. If you don't do that then you have to implement your own garbage collector and pay the penalty periodically.

> If you remove a node in the list now you have to rewrite all the values in the links array.

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

Link shape:

  Occupied Nodes: 0 -> 2 -> 3 -> 4 -> []
  Free Nodes: 1 -> []

To Delete C:

  data[2] = empty // free data
  links[2] = 1 // Repoint 2 -> 1
  links[0] = 3 // Repoint 0 -> 3
  firstFreeNode = 1

This changes the data such:

  Data: [ a, 0, 0, d, e ]
  Links: [ 3, 2, -1, 4, -1 ]

  Head of occupied nodes: 0
  Head of free nodes: 2

New shape:

  Occupied Nodes: 0 -> 3 -> 4 -> []
  Free Nodes: 2 -> 1 -> []

Is there a reason the keep the data and the indices in different arrays? Unless you're navigating to an item by its position in the linked list, you're going to be checking the data at each node and then reading the next index to traverse forward. Since you're reading both, wouldn't it be better to make the index of the next node intrusive?

The design is mostly to provide a clear enough example, you can of course interlace them.

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 allows you to reorder the data, say sorting it, without moving the actual data. If the element type is say a struct, this can be a huge performance win.

It also allows you to keep multiple different lists to the same data, say sorted by different fields in the struct.

Operating systems where you need to be able to atomically insert or remove from a list. Because the links are just pointers and the memory can be managed after the swap you can use atomics to compare and swap pointers. This allows for the RCW mechanisms the linux and NT kernels depend on to work.

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.

One nice property is their stable addressing. A linked list element won't move once allocated.

> A linked list element won't move once allocated.

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).

A reference in Java can essentially be thought of as a pointer into a virtual address space. The JVM can move around the location of an object in the system's actual memory, but as far as anything holding reference is concerned nothing has changed.

And a reference to an object that's in an array won't be invalidated if that object is moving around the array or even removed entirely. It's still a C concern.

I believe they can also be useful to share data between instances in the case of immutable structure. Prepending to an immutable linked list is quasi-free in terms of memory usage.

Anytime you do something that is immutable with probable change somewhere inside that is not easy to handle with far mor complex datastructure. In particular linked list are great for heterogeneous cells type.

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.

Why not just implement this as an array of constant width pointers to the heterogeneous data types?

Which is what happens in most modern languages. The items in your list are objects--which internally are just pointers to the data. There's no performance penalty for having variable-sized objects in the list.

you just defined how memory work, you are welcome :)

Linked lists are great for free lists in memory allocators.

"When are linked lists actually good?"

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.

> "*I can't quite remember the marketing term that was used. It's a dead term now because everything works that way.)"

The term I remember was 486DX2-66 , so was it DX2?

https://en.wikipedia.org/wiki/Intel_DX2

I would think a queue would be best served by a linked list.

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.

Circular buffers (your fancy implementation) are far superior for queues. Pretty much any modern vector like data structure is already going to have grow logic so adding head and tail pointers isn't too hard. However, as this article mentions, keeping memory compact is pretty important to speed, and circular buffers are able to do that while linked lists aren't.

By data structure standards, the requisite amount of "fanciness" to implement a queue in a vector is table stakes, hardly even worth 10 minutes of class time at the sophomore level, if not simply given out as homework. It is no problem at all to put a queue in a vector. You'd need a doubly-linked list for this, too, and as the article mentions, your linked-list queue is likely to lose just on malloc & free (or local equivalents) versus the vector.

(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 majority of microprocessors today are <200MHz, single core, single issue, with no cache. The world doesn't run on x64 and GPUs.

I have seen highly successful proprietary trading firms implement their order books using linked lists (more like a linked list for each level of the order book, with the levels themselves arranged in a linked list). Obviously they use a custom allocator or an object pool to make sure that the cache performance isn't completely atrocious.

They are sometimes used as intrusive lists but a generic one rarely used.

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