One of the only times linked lists are “undoubtedly the right option” is if you’re writing some sort of intrusive data structure to avoid an allocation by reusing caller stack from another location. Not sure how many run into that often.
Also in an osdev context, where you have drivers/filters/etc that chain operations to the next installed one, etc. and you want the control flow to be left to each filter/driver/etc in turn rather than making the decision top-down.
Linked lists are great for stack or queue data structures. They have O(1) insert at the start and ends. Traversal is painful for caches but inserting at one end and removing from either that end or the other end are very fast and does not require allocation. There are a lot of situations where those are useful properties. They also allow constant-time insertion into the middle.
Doubly linked lists allow constant-time insertion removal from middle without traversal. Array-like data structures are linear complexity for this. Again, this is a useful property for some use cases.
Linked lists are really bad for cache usage (and TLB pressure) for traversal. If your algorithm requires iterating over the list anywhere near a hot path, they’re probably the wrong data structure.
The problem with the use cases you listed can sometimes be the 8-16 bytes of extra memory per item are rather inefficient. For that, you often just use linked list of arrays to amortize the pointer size across multiple items.
You only safe that overhead if the objects are inline in the arrays, but then removal is more expensive because you either defragment the array with copies (cost scales with object size) or you have more expensive search for the next element (lots of data dependent branches to hurt prediction).
Lists of arrays are great for things like text, where you want fast iteration and fairly cheap insertion. There, though, the goal isn’t to amortise the cost of the pointer (though that’s a nice benefit), it’s to improve cache locality on traversal. If the list elements are cache-line aligned then you can also vectorise most per-character operations with the widest vector unit available and get good performance. Even in this use case though, you often want random access and so use a richer indexing structure than a list.
Not being dense at all; it’s not something most people use outside of low-level dev. Instead of having a list that exists independent of the object(s) and storing the objects in the list, the list is incorporated into the structure of the object (not very OOP!). The clever part is that these objects may be pre-existing in very different contexts/locations (such as the stacks of callers in different threads) and so you now have a way to navigate between all these objects without having dynamically allocated them anywhere.
It’s also used as an esoteric concept for writing performant low-level multithreading primitives or frameworks.
Thread A wants to acquire a user-space mutex. Instead of the mutex containing a vector of some struct { thread_id, timeout, etc } and need to dynamically allocate, reallocate, etc all that each time a new thread is waiting on the mutex, Thread A reserves space for that structure (with an additional next pointer in it now) on its stack inside the mutex.wait() function but before the actual blocking wait is carried out internally. The mutex just has a single pointer current_waiter that’s either null or the first thread to block waiting for the mutex. Thread A either sets current_waiter to point to the area it reserved on its own stack or traverses the what-we-now-call-intrusive linked list to add itself at the end (no allocations needed).
Also, intrusive data structures let you do crazy things like store the same object in multiple lists/trees at once without needing to refcount.
(Disclaimer: 30 years systems programming, still going strong…)
“One of the only times.. intrusive data structure.. stack re-use”
I don’t necessarily agree with this framing. I’d prefer to say, you can make extreme gains by using a linked list, for as long as you well-order your data according to performance requirements .. whereby the stack is hardly relevant as anything but pointer angels pointing to a haven of text segments.
I was one of the voices saying that I wish people had some other go to datastructure than linked lists for learning a new language.
Mainly because I love Rust (especially the borrow checker), and I hate the idea people get turned off the language due to ownership rules messing with their first attempt coding something.
Thanks for sharing that link. I fear I have permanently lost some coding iq from stepping through the (mentally corrected) version of the code sample from that page.
Wheter Rust is a good first language, I don’t know. I think it could be, because there’s plenty of stuff you can do without being even close to “fight the borrow checker”.
Maybe it comes down to whether teaching pass by reference vs value is something that’s OK to learn early or not.
The borrow checker vs linked lists conflict is so unfortunate. I wonder if borrow checking hasn’t been done before, because every time a language researcher considered such design they’ve thought “it won’t even work on linked lists, obviously a dead-end idea”.
I wonder if borrow checking hasn’t been done before, because every time a language researcher considered such design they’ve thought “it won’t even work on linked lists, obviously a dead-end idea”.
I think the historical record (read: breadcrumbs through the literature) suggests otherwise; there’s been continual progress on this kind of thing stretching back 30 years (some original type theory work in the early 90’s, some work on applying it to systems programming in the context of Cyclone in the early 00’s, various research-grade projects, and Rust first showed up on the scene in 2010 but it takes a while for a language to become mature). I think the reason it hasn’t been done before is because it wasn’t actually trivial figuring out how, and it took a while to get there.
I wonder if borrow checking hasn’t been done before, because every time a language researcher considered such design they’ve thought “it won’t even work on linked lists, obviously a dead-end idea”
This makes me wonder if a prerequisite for Rust’s creation was a critical mass of people who all hold the opinion “eh, linked lists suck anyway, no big deal”.
prerequisite for Rust’s creation was a critical mass of people who all hold the opinion “eh, linked lists suck anyway, no big deal”.
I don’t know why this is how people think about rust. For me, as a low-level dev that does tons of crazy stuff that isn’t necessarily borrowck-friendly, I just figured “free safety checks when/where possible” then back to unsafe when I can’t. It’s not like you lose anything compared to before, you just don’t get to take advantage of the safety guarantees the language has to offer as much as you would like to at all times.
(I also don’t end up reaching for unsafe as often as I thought I would.)
The Rust community is pretty big now, and opinions on unsafe vary a lot. Some people write really twisted or inefficient code just to avoid unsafe {}. I guess it depends whether you see Rust as safer C, or faster Python.
People who have only programmed in high level languages (with their “LinkedList” classes) don’t know or understand what real linked lists are. Linked lists aren’t separate objects that need to be allocated; generally, in C or assembly, the total number of additional allocations for maintaining a few dozen linked lists of a few thousand nodes each is … zero.
Here’s an example of a Person “object” 🤣 in C, plus a couple of linked lists and a binary tree:
We’ve gotten so spoiled by the low cost of allocation and GC that linked lists have gone out of style. (It’s also worth nothing that integrated linked lists in structures is fairly brittle and not easily concurrent-safe.)
Yes, of course you are absolutely correct; I was exaggerating for effect.
One thinks about data structures much differently when the data itself is an integral part of the data structure, versus when the data structure is a separately managed unit, and the data that is stored in the data structure has no awareness of the data structure.
Obviously, all other things equal, the separation of concerns is a huge win. But what I think most people have found, with simple data structures such as linked lists, is that once the concerns are separated, there are very few reasons remaining to use a generic “linked list” data structure. It is almost always: (i) dramatically heavier (both memory footprint and allocation count), and (ii) slower than the alternatives. In other words, it’s almost always a lose/lose.
The last 100+ times that I’ve seen someone using the LinkedList class in Java or C# have all been wrong. As in, an obviously wrong choice of data structure to use. And from a hiring perspective, it’s almost an automatic disqualifier.
I think cleverness of intrusive linked lists is overblown. In typical cases it’s just a hand-rolled Node<Person> in languages that don’t have both generics and value types.
It’s not that linked lists in primitive languages are particularly clever; it’s more that there was nothing else available (for the definition of “available” in a highly constrained language with a pathetic type system running in a highly constrained hardware environment). It’s the proverbial “when the only tool that you have is a hammer….”
The weird thing for me was realizing (not that long ago) how dependent on linked lists I was in C, and simultaneously realizing that I never used them in Java or C#. I really had to stop and think about it (and reason it through), even though now in retrospect it’s perfectly obvious to me why things naturally are this way.
The other thing to remember in those primitive languages (and C and C++ are primitive languages, regardless of the progress that standards bodies continue to make 50 and 60 years after the languages’ creation) …
Apologies, run-on parenthesized thoughts are a bit annoying. Let me start again:
The other thing to remember in those primitive languages is that the Node<Person> that you referred to was often a node in a bunch of separate logical linked lists and binary trees (etc.) A developer would just continue to add pointers to the struct any time that a new relationship had to be supported or a new look-up mechanism was required. Need a linked list to be a bi-directional list? Just add a prevX pointer. Need a linked list to be a tree? Just replace nextX with both a leftX and a rightX. Need that tree to be walkable? Just add parentX. Need it to be balanced? Just add an int redX : 1; field. 🤣 And of course, every time you add a field, you have to add a pile of code everywhere to support it. And none of it is concurrent-safe. So I’m not arguing that we should ever “go back” to that mess. It’s more that I’m realizing why that mess had to exist within those languages and with the constraints that we had at the time (one slow CPU, no multi-threading or concurrency, tiny amount of memory).
I mean you can write Person {name, next, prev} or Node<T> { T, next, prev }, and it ends up exactly the same in memory. With a little bit of type-system wrangling you could make it nest too (TreeNode<ListNode<Person>>), and support node existing in multiple trees/lists.
But I’m suspicious whether one node living in multiple lists at the same time is wise and performant. It makes memory ownership unclear (and complex if it’s a shared ownership). You already have to dereference pointers, so I don’t see a major difference between a Person living in multiple linked lists or multiple contiguous arrays of pointers to Person (removals from the middle can be cheap with swap-remove, still cheap with smallish sizes when copying, and you can use a rope for large arrays). If you want to optimize for traversing only subsets like “person with an address”, then SOA or ECS-style storage is going to be faster and more memory-efficient.
Architecturally, git is a key-value database of objects that represent an acyclic graph of commits and a tree of directories/files. A simple case of linear commits is a linked list indeed, but that’s not the programming-language-level linked list that the post is about.
Implementing something with libgit2 is another good way to learn the finest of the details. It’s thrilling to make a program that can construct a branch, tree, commit, etc and then have git show it to you.
I’ve learned it the hard way, but these days there’s a bunch of tutorials about git inner workings. I highly recommend learning it, because it makes git make sense.
The arguments against linked lists are about memory cache locality, lack of CPU SIMD autovectorization, CPU pipeline stalls from indirection, etc., so the memory vs file system difference is important.
Linked lists on a file system are problematic too. Disks (even SSD) prefer sequential access over random access, so high-performance databases usually use btrees rather than lists.
git’s conceptually simple model is more complicated when you look at implementation details of pack files (e.g. recent commits may be packed together in one file to avoid performing truly random access over the whole database).
Yeah, Git is similar to a Merkle Tree, which shares a lot in common with a single linked list, in that from HEAD you can traverse backwards to the dawn of time. However it differs because merge commits cause fork/join patterns that lists aren’t supposed to have.
Interesting. I was looking into how to reproduce merge commits (oids) from someone else’s working tree that push to the same bare repo (e.g. on Github). I was forced to calculate a sha256 to verify that the actual committed files are the same between to working trees. Know there must be a lighter more efficient way. Probably would be a real nasty looking one-liner though.
Admittedly, one of my favorite questions to ask new grads is if they can explain at any level of detail they feel comfortable the difference between an array and a linked list.
I am always baffled at the answers - it seems about 1/3 of people say “aren’t they the same thing?” and I quietly weep the rest of the interview. Not saying they can’t learn, but the differentiation between an array and a list has been lost in the switch from C/C++/Java -> Python as the “main” education language (imo).
We went with a linked list in a recent thing we launched. The nodes are actually referenced by cryptographic hashes - the hashes uniquely identify the data structure for a whole bunch of other subsystems.
Good question. Each node is generated by an actual human that ultimately did something intentional to trigger in the UI - it takes a lot of non-trivial work by them. Generally the list won’t be more than what you can count on your fingers. Should put a cap just in case of a malicious user or some weird corner case of some script someone is using goes haywire - but sorta protected right now because essentially someone would have to ddos a popular third party service that has an excellent rate limit system - no risk of stack overflow in practical terms. When we create an independent system to interact that creates linked list nodes, would be a concern I suppose.
One of the only times linked lists are “undoubtedly the right option” is if you’re writing some sort of intrusive data structure to avoid an allocation by reusing caller stack from another location. Not sure how many run into that often.
Also in an osdev context, where you have drivers/filters/etc that chain operations to the next installed one, etc. and you want the control flow to be left to each filter/driver/etc in turn rather than making the decision top-down.
Linked lists are great for stack or queue data structures. They have O(1) insert at the start and ends. Traversal is painful for caches but inserting at one end and removing from either that end or the other end are very fast and does not require allocation. There are a lot of situations where those are useful properties. They also allow constant-time insertion into the middle.
Doubly linked lists allow constant-time insertion removal from middle without traversal. Array-like data structures are linear complexity for this. Again, this is a useful property for some use cases.
Linked lists are really bad for cache usage (and TLB pressure) for traversal. If your algorithm requires iterating over the list anywhere near a hot path, they’re probably the wrong data structure.
The problem with the use cases you listed can sometimes be the 8-16 bytes of extra memory per item are rather inefficient. For that, you often just use linked list of arrays to amortize the pointer size across multiple items.
You only safe that overhead if the objects are inline in the arrays, but then removal is more expensive because you either defragment the array with copies (cost scales with object size) or you have more expensive search for the next element (lots of data dependent branches to hurt prediction).
Lists of arrays are great for things like text, where you want fast iteration and fairly cheap insertion. There, though, the goal isn’t to amortise the cost of the pointer (though that’s a nice benefit), it’s to improve cache locality on traversal. If the list elements are cache-line aligned then you can also vectorise most per-character operations with the widest vector unit available and get good performance. Even in this use case though, you often want random access and so use a richer indexing structure than a list.
Could you give a code example of that usecase? I’m a bit dense today.
Not being dense at all; it’s not something most people use outside of low-level dev. Instead of having a list that exists independent of the object(s) and storing the objects in the list, the list is incorporated into the structure of the object (not very OOP!). The clever part is that these objects may be pre-existing in very different contexts/locations (such as the stacks of callers in different threads) and so you now have a way to navigate between all these objects without having dynamically allocated them anywhere.
It’s also used as an esoteric concept for writing performant low-level multithreading primitives or frameworks. Thread A wants to acquire a user-space mutex. Instead of the mutex containing a vector of some
struct { thread_id, timeout, etc }and need to dynamically allocate, reallocate, etc all that each time a new thread is waiting on the mutex, Thread A reserves space for that structure (with an additionalnextpointer in it now) on its stack inside themutex.wait()function but before the actual blocking wait is carried out internally. The mutex just has a single pointercurrent_waiterthat’s either null or the first thread to block waiting for the mutex. Thread A either setscurrent_waiterto point to the area it reserved on its own stack or traverses the what-we-now-call-intrusive linked list to add itself at the end (no allocations needed).Also, intrusive data structures let you do crazy things like store the same object in multiple lists/trees at once without needing to refcount.
I do this quite often. It’s basically a stack-allocated linked list where nodes reside in different frames of the call stack. Here is one example: https://github.com/build2/libbutl/blob/master/libbutl/diagnostics.hxx#L284
Another common case where I tend to use a list instead of a vector is when I need iterator and/or node stability.
(Disclaimer: 30 years systems programming, still going strong…)
“One of the only times.. intrusive data structure.. stack re-use”
I don’t necessarily agree with this framing. I’d prefer to say, you can make extreme gains by using a linked list, for as long as you well-order your data according to performance requirements .. whereby the stack is hardly relevant as anything but pointer angels pointing to a haven of text segments.
This is the tweet that I believe prompted the blog post. https://twitter.com/antirez/status/1587581541022142464
I was one of the voices saying that I wish people had some other go to datastructure than linked lists for learning a new language.
Mainly because I love Rust (especially the borrow checker), and I hate the idea people get turned off the language due to ownership rules messing with their first attempt coding something.
Now I’m wondering how many C books and tutorials include buggy linked lists with behavior worse than O(n) append.
There are some pretty bad C books, and even good ones do have errors. https://wozniak.ca/blog/2018/06/25/1/index.html
Thanks for sharing that link. I fear I have permanently lost some coding iq from stepping through the (mentally corrected) version of the code sample from that page.
It’s totally fine if Rust is not a good choice for somebody’s first language. C++ is a horrible first language, as are several others.
Yeah. I meant “coding something in Rust”.
Wheter Rust is a good first language, I don’t know. I think it could be, because there’s plenty of stuff you can do without being even close to “fight the borrow checker”.
Maybe it comes down to whether teaching pass by reference vs value is something that’s OK to learn early or not.
The borrow checker vs linked lists conflict is so unfortunate. I wonder if borrow checking hasn’t been done before, because every time a language researcher considered such design they’ve thought “it won’t even work on linked lists, obviously a dead-end idea”.
I think the historical record (read: breadcrumbs through the literature) suggests otherwise; there’s been continual progress on this kind of thing stretching back 30 years (some original type theory work in the early 90’s, some work on applying it to systems programming in the context of Cyclone in the early 00’s, various research-grade projects, and Rust first showed up on the scene in 2010 but it takes a while for a language to become mature). I think the reason it hasn’t been done before is because it wasn’t actually trivial figuring out how, and it took a while to get there.
This makes me wonder if a prerequisite for Rust’s creation was a critical mass of people who all hold the opinion “eh, linked lists suck anyway, no big deal”.
I don’t know why this is how people think about rust. For me, as a low-level dev that does tons of crazy stuff that isn’t necessarily borrowck-friendly, I just figured “free safety checks when/where possible” then back to
unsafewhen I can’t. It’s not like you lose anything compared to before, you just don’t get to take advantage of the safety guarantees the language has to offer as much as you would like to at all times.(I also don’t end up reaching for
unsafeas often as I thought I would.)The Rust community is pretty big now, and opinions on
unsafevary a lot. Some people write really twisted or inefficient code just to avoidunsafe {}. I guess it depends whether you see Rust as safer C, or faster Python.I’ll bite my tongue here and refrain from saying anything other than I agree with you.
Ah, this is a very good way to look at it
Anyone know what Rust blog post antirez was reading?
People who have only programmed in high level languages (with their “LinkedList” classes) don’t know or understand what real linked lists are. Linked lists aren’t separate objects that need to be allocated; generally, in C or assembly, the total number of additional allocations for maintaining a few dozen linked lists of a few thousand nodes each is … zero.
Here’s an example of a Person “object” 🤣 in C, plus a couple of linked lists and a binary tree:
We’ve gotten so spoiled by the low cost of allocation and GC that linked lists have gone out of style. (It’s also worth nothing that integrated linked lists in structures is fairly brittle and not easily concurrent-safe.)
That’s an intrusive linked list; certainly other linked lists are also “real”.
Yes, of course you are absolutely correct; I was exaggerating for effect.
One thinks about data structures much differently when the data itself is an integral part of the data structure, versus when the data structure is a separately managed unit, and the data that is stored in the data structure has no awareness of the data structure.
Obviously, all other things equal, the separation of concerns is a huge win. But what I think most people have found, with simple data structures such as linked lists, is that once the concerns are separated, there are very few reasons remaining to use a generic “linked list” data structure. It is almost always: (i) dramatically heavier (both memory footprint and allocation count), and (ii) slower than the alternatives. In other words, it’s almost always a lose/lose.
The last 100+ times that I’ve seen someone using the LinkedList class in Java or C# have all been wrong. As in, an obviously wrong choice of data structure to use. And from a hiring perspective, it’s almost an automatic disqualifier.
I think cleverness of intrusive linked lists is overblown. In typical cases it’s just a hand-rolled
Node<Person>in languages that don’t have both generics and value types.I don’t think that this is true 🤷♂️
It’s not that linked lists in primitive languages are particularly clever; it’s more that there was nothing else available (for the definition of “available” in a highly constrained language with a pathetic type system running in a highly constrained hardware environment). It’s the proverbial “when the only tool that you have is a hammer….”
The weird thing for me was realizing (not that long ago) how dependent on linked lists I was in C, and simultaneously realizing that I never used them in Java or C#. I really had to stop and think about it (and reason it through), even though now in retrospect it’s perfectly obvious to me why things naturally are this way.
The other thing to remember in those primitive languages (and C and C++ are primitive languages, regardless of the progress that standards bodies continue to make 50 and 60 years after the languages’ creation) …
Apologies, run-on parenthesized thoughts are a bit annoying. Let me start again:
The other thing to remember in those primitive languages is that the
Node<Person>that you referred to was often a node in a bunch of separate logical linked lists and binary trees (etc.) A developer would just continue to add pointers to the struct any time that a new relationship had to be supported or a new look-up mechanism was required. Need a linked list to be a bi-directional list? Just add aprevXpointer. Need a linked list to be a tree? Just replacenextXwith both aleftXand arightX. Need that tree to be walkable? Just addparentX. Need it to be balanced? Just add anint redX : 1;field. 🤣 And of course, every time you add a field, you have to add a pile of code everywhere to support it. And none of it is concurrent-safe. So I’m not arguing that we should ever “go back” to that mess. It’s more that I’m realizing why that mess had to exist within those languages and with the constraints that we had at the time (one slow CPU, no multi-threading or concurrency, tiny amount of memory).I mean you can write
Person {name, next, prev}orNode<T> { T, next, prev }, and it ends up exactly the same in memory. With a little bit of type-system wrangling you could make it nest too (TreeNode<ListNode<Person>>), and support node existing in multiple trees/lists.But I’m suspicious whether one node living in multiple lists at the same time is wise and performant. It makes memory ownership unclear (and complex if it’s a shared ownership). You already have to dereference pointers, so I don’t see a major difference between a
Personliving in multiple linked lists or multiple contiguous arrays of pointers toPerson(removals from the middle can be cheap with swap-remove, still cheap with smallish sizes when copying, and you can use a rope for large arrays). If you want to optimize for traversing only subsets like “person with an address”, then SOA or ECS-style storage is going to be faster and more memory-efficient.Correct me if I’m wrong, but doesn’t git basically work in some way using linked lists to do certain things?
Architecturally, git is a key-value database of objects that represent an acyclic graph of commits and a tree of directories/files. A simple case of linear commits is a linked list indeed, but that’s not the programming-language-level linked list that the post is about.
Okay that makes sense about commits. How did you learn about the inner-workings of git?
I’ve found the official (free) book to be an excellent source.
https://git-scm.com/book/en/v2
Obviously not every part is relevant to you, skip what isn’t, but I found it generally well written and useful.
This is another great resource for learning how git works internally: http://aosabook.org/en/git.html
Implementing something with libgit2 is another good way to learn the finest of the details. It’s thrilling to make a program that can construct a branch, tree, commit, etc and then have
gitshow it to you.I’ve learned it the hard way, but these days there’s a bunch of tutorials about git inner workings. I highly recommend learning it, because it makes git make sense.
The only difference I see is that it’s implemented in the file system instead of in memory.
The arguments against linked lists are about memory cache locality, lack of CPU SIMD autovectorization, CPU pipeline stalls from indirection, etc., so the memory vs file system difference is important.
Linked lists on a file system are problematic too. Disks (even SSD) prefer sequential access over random access, so high-performance databases usually use btrees rather than lists.
git’s conceptually simple model is more complicated when you look at implementation details of pack files (e.g. recent commits may be packed together in one file to avoid performing truly random access over the whole database).Thanks for that context!
Yeah, Git is similar to a Merkle Tree, which shares a lot in common with a single linked list, in that from HEAD you can traverse backwards to the dawn of time. However it differs because merge commits cause fork/join patterns that lists aren’t supposed to have.
Interesting. I was looking into how to reproduce merge commits (oids) from someone else’s working tree that push to the same bare repo (e.g. on Github). I was forced to calculate a sha256 to verify that the actual committed files are the same between to working trees. Know there must be a lighter more efficient way. Probably would be a real nasty looking one-liner though.
A major contributor to the beauty which is AmigaOS.
Would you care to explain? :)
Are you talking about this?
Admittedly, one of my favorite questions to ask new grads is if they can explain at any level of detail they feel comfortable the difference between an array and a linked list.
I am always baffled at the answers - it seems about 1/3 of people say “aren’t they the same thing?” and I quietly weep the rest of the interview. Not saying they can’t learn, but the differentiation between an array and a list has been lost in the switch from C/C++/Java -> Python as the “main” education language (imo).
We went with a linked list in a recent thing we launched. The nodes are actually referenced by cryptographic hashes - the hashes uniquely identify the data structure for a whole bunch of other subsystems.
Do you protect from getting a stack overflow when dropping a long chain?
Good question. Each node is generated by an actual human that ultimately did something intentional to trigger in the UI - it takes a lot of non-trivial work by them. Generally the list won’t be more than what you can count on your fingers. Should put a cap just in case of a malicious user or some weird corner case of some script someone is using goes haywire - but sorta protected right now because essentially someone would have to ddos a popular third party service that has an excellent rate limit system - no risk of stack overflow in practical terms. When we create an independent system to interact that creates linked list nodes, would be a concern I suppose.