61–70 of 131 posts
> Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects. I beg to disagree. In kernels, drivers, and embedded systems they are very common.
Why? Why would someone reach for a linked list in a kernel, driver, or embedded system?
Earlier quoted context omitted.
Why? Why would someone reach for a linked list in a kernel, driver, or embedded system?
Easier to avoid allocation errors, e.g. in the Linux kernel. I think Alice Ryhl mentioned it here - https://www.youtube.com/watch?v=CEznkXjYFb4
My experience in embedded, everything is hardcoded as a compile time constant, including fixed size arrays (or vectors of a fixed capacity)
Yes, if you have a simple choice between a vector and a linked list, then the vector is vastly superior due to locality and (for non-intrusive linked lists) allocations. So much so that vectors often win even when you're doing lots of O(n) deletions that would be O(1) with a linked list.
But that doesn't mean that linked lists are useless! A vector gives you a single ordering. What if you need multiple? What if you need a free list, which you're never going to be iterating over but will just grab off an item at a time? I find it quite common to have one "natural" order, for which I will use a vector (or equivalently, a bump allocator of fixed-size items), and then one or several auxiliary orders like the entries belonging to a particular owner or the ones that will need to be visited for some sort of cleanup or an undo list or some sort of stack or queue of pending items to process. Your common iteration will be in memory order, but that doesn't mean you won't ever want to do different iterations.
It annoys me that this is always omitted, with the attitude that linked lists are obsolete and useless because vectors be moar better faster gooder, to the point that it's a waste of time to learn how to manipulate linked lists anymore.
I guess a lot of this is probably due to the popularity of high level languages, where you're just dealing with references to everything in the first place. But in those, the arguments in favor of vectors are often not valid because that blessed golden vector of Objects is giving you no more locality than giving your Object a `next` field: the vector of Objects is represented internally as a vector of pointers to the actual Object data, so your oh so nicely cached lookups are doing memory reads that are 100% pure overhead compared to following a `next` link from an Object that fits into a cache line. In both cases, your performance is going to be limited by the locality of your Object data, which is the same whether you have a vector of pointers or Object data with an intrusive pointer.
Also, if you have an existing setup and need to introduce a new list, it is sometimes far easier to drop in a `next` (and maybe `prev`) field than to refactor everything to accommodate a new vector. Especially since the vector will move all of your data when resizing the vector, which invalidates any pointers you might be using for other purposes. If you'll be iterating that list frequently, then the vector may very well be a good idea. If it's just for error cases or slow paths, then linked lists really aren't bad at all.
I'm not trying to argue for linked lists here so much as arguing against the blanket arguments against them.
Earlier quoted context omitted.
The entire theoretical advantage of linked lists over vectors (constant time insertion and deletion) comes from not sequentially allocating them.
If you have a compacting GC you are going to move the nodes anyway, so why not reallocate them sequentially?
Earlier quoted context omitted.
Easier to avoid allocation errors, e.g. in the Linux kernel. I think Alice Ryhl mentioned it here - https://www.youtube.com/watch?v=CEznkXjYFb4
How do linked list prevent allocation errors? If anything it would seem to make them worse. My experience in embedded, everything is hardcoded as a compile time constant, including fixed size arrays (or vectors of a fixed capacity)
Earlier quoted context omitted.
Instead of thinking of a linked list structurally, think of it functionally. You can have a token that represents a location in the linked list. From that token you have a Fetch() operation that will fetch what is at that location, a Next() operation that will fetch the next token or some indication that you are done, and depending on your language, some sort of insert or append operation (mutability factors in here)…
Linked lists are, by definition, a value with a pointer to the next. That's what makes it "linked". The API you're describing is the iterator pattern, which indeed can be backed by almost anything (be it a linked list, array, tree, etc.).
But just because Lisp has cons and cdr does not mean the compiler is obligated to only and exactly use things that structurally look like linked lists in the actual implementation. You need to break the relationship between memory layout and API to understand what is going on here. You may choose later to put them back together; the naive memory layout is often a good one. (Linked lists nowadays are arguably one of the larger exceptions to that, but there are still circumstances even so where that may not be an issue; see Erlang's memory management for instance and ponder how that impacts linked list locality.) But you can't understand what compilers may be doing if you do not realize that there is a distinction.
Linked list benchmarks are amazing.... if you don't thrash your cache on inserts so all its elements are contiguous. You get all the benefits of a vector and a linked list, without the reality that linked lists mostly don't get populated 100% consecutively, and thus can be anywhere in memory.
Benchmarking is hard, and very often is done in ideal conditions, which never materialize in real use cases.
Earlier quoted context omitted.
Instead of thinking of a linked list structurally, think of it functionally. You can have a token that represents a location in the linked list. From that token you have a Fetch() operation that will fetch what is at that location, a Next() operation that will fetch the next token or some indication that you are done, and depending on your language, some sort of insert or append operation (mutability factors in here)…
> Instead of thinking of a linked list structurally, think of it functionally If your argument is that a linked-list-like data structure can be implemented using something other than a linked list, then I agree with you. Vector tries (for example) are great for that use case. But a vector trie isn't a linked list, it's a vector trie. As such, it will be faster for some usage patterns, equal for some, and completely d…
Linked lists get a bum rap. Yes, if you have a simple choice between a vector and a linked list, then the vector is vastly superior due to locality and (for non-intrusive linked lists) allocations. So much so that vectors often win even when you're doing lots of O(n) deletions that would be O(1) with a linked list. But that doesn't mean that linked lists are useless! A vector gives you a single ordering. What if you…
You can very much have a single vector owning the memory, and do all other ordering over auxiliary vectors of indices. Should be cheaper and faster than holding more linked lists.
If you want to remove elements, you can very much use tombstones to flag deleted elements and then clean up after some threshold.
> Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects. I beg to disagree. In kernels, drivers, and embedded systems they are very common.
Why? Why would someone reach for a linked list in a kernel, driver, or embedded system?