Hacker News Reader

Comment by scottlamb | Hacker News Reader

> I thought of writing this blog post full of all the things I love about linked lists.

The blog post is short, and I think the author covered about everything.

Yeah, linked lists are sometimes appropriate, especially intrusive linked lists (the author called them "embedded" linked lists). The hate they get is a backlash against CS programs that introduce people to them early and don't emphasize enough the reasons you should usually pick something else. If we have to err on one side or the other, I'd rather it be telling people not to use them.

btw:

> Redis can be wrong, but both Redis and the Linux kernel can’t.

Yes, they can, and I'd rather avoid argument from authority altogether.

View on HN

Both Redis and Linux are C projects, and in C it's customary to roll your own containers. Without generics, and with a culture of avoiding small dependencies, it's preferred to roll your own simple list than to reach for more advanced reusable data structures.

So I don't think it's a particularly enlightened decision by these projects to use so many lists on their merit, but rather a programming pattern especially common in the C language they use.

Meh, that's true of some C projects, but AFAIK Linux/Redis have good reasons here, and if I were to criticize Linux for something, it wouldn't be unwillingness to write more code.

I still prefer to evaluate each decision on its merits. Linux has made some great decisions. Also some terrible ones—e.g. fsync semantics [1], attitude to fuzzing. Redis probably has too. They can agree on something and be wrong.

[1] https://wiki.postgresql.org/wiki/Fsync_Errors

If you have a pointer to an element of a doubly liked list, you can always remove it in a few processor cycles. You can also always add or remove from the end of front of the list in a few cycles.

This means that you can do those things under a spin lock or with interrupts masked. You cannot really resize a dynamic array under a tight spinlock, or modify a tree that should be kept balanced.

Another use case is free lists, a list of preallocated structures where you can grab one or put one back quickly under spinlock.

These are some examples of how lists are used in kernel land.

I'm not saying there are no uses. Concurrent lock-free algorithms are an especially useful case, and a e.g. linked list of on-stack mutex waiters is a very clever approach that I don't think has a better replacement. But I doubt that lists are as common as they are because every place really needs them.

Vecdeque can cheaply pop/push front and end too. Arrays have swap-remove. You may not need to grow if you preallocated a capacity. Freelists can be a stack, or you can choose a data structure that doesn't allocate objects individually so you don't need the freelist in the first place.

Another thing that is C-specific is that most objects are treated as unmovable and their address is their permanent identity. Without language features for prevention of dangling pointers, moves are asking for trouble. This favors linked lists and pointery data structures over contiguous containers and inlined data.

> > Redis can be wrong, but both Redis and the Linux kernel can’t.

> Yes, they can, and I'd rather avoid argument from authority altogether.

Pretty sure that was a joke, considering the overall light-heartedness of the whole post.

Ahh, you're probably right. I missed it.

The problem with linked lists is that they are rarely the ideal solution to any problem. They are convenient in C, because of C’s inadequacies, but in C++ and Rust they are marginalized because the tools exist to use superior data structures.

You almost always want to unroll your linked linked lists, so that items are fetched in blocks. But this rarely happens in C because it’s premature optimization in C. In C++ or Rust you can write the code once in a generic data structure and enjoy the benefits to the end of time.

That all said, I think we should still teach them in CS because understanding linked lists is the first step to understanding trees.

OS kernels tend to use them simply because they don't have malloc at their disposal and so it's most practical to stick to fixed size memory chunks, right?

Linux kernel's malloc is probably more resilient to the long-term (as in, long running) problems you would get from continually resizing an array with realloc in userspace (ie. massive heap fragmentation and eventually dying in flames)

>Yes, they can, and I'd rather avoid argument from authority altogether.

Proof by authority is the worst. Yet, linux kernel can have valid reasons for, but they are intrusive lists with the data having a pointer to the next.

Reply on news.ycombinator.com