31 ms·

In defense of linked lists

603 points by grep_it 4y ago

swellguy 4y ago
I think this article could be more intelligently titled: "Don't post, read, or respond to things on TWTR". The linked lists aspect could be replaced with anything.
TillE 4y ago
The Windows kernel also has linked lists as one of its few general-purpose data structures available to drivers. Like any tool, it has its place. As long as you're not traversing large linked lists, they're probably fine.
- dilyevsky 4y ago
  Traversing a short list but frequently still going to have terrible cache performance compared to something like vector. Just use vectors, folks
  - deleted 4y ago
    [deleted]
  - slaymaker1907 4y ago
    Allocating a huge chunk of memory all at once when the array grows can also cause a bunch of problems. Linked lists are also much simpler in a multi threaded context.
    - dilyevsky 4y ago
      I’m not an expert in memory allocators but I suspect large allocation is better than many small allocs due to less fragmentation no? I’ll grant you the multithreaded case but if you’re doing that your cache performance is probably crap anyway =)
dragontamer 4y ago
The most interesting thing about linked lists to me is how trivially it can be made lock-free multithreaded with atomics. An array/stack can be made multithreaded but it is non-trivial to handle the edge-cases. In particular, the ABA problem is rather difficult. I've seen many solutions to it (ex: a synchronization variable that puts the stack into "push-only" mode and then "pop-only" mode. There's no ABA-problem if all threads are pushing!) However, pushing/popping from a Linked List stack requires no such synchronization at all. Simply compare-and-swap the head (and on failure, try again). Its about as simple as you can get when it comes to atomic / lock free patterns.
- yeputons 4y ago
  > Simply compare-and-swap the head (and on failure, try again). It doesn't help with ABA at all, does it? Unless you assume that nodes are immutable and the same pointer is never reused, of course.
  - dragontamer 4y ago
    I forgot about that other ABA issue. Still, that's easily solved: 64-bit version number + 64-bit pointer (or 32-bit version number + 32-bit pointer) for a 128-bit (or 64-bit) compare-and-swap. All modern CPUs support 128-bit CAS. EDIT: The version number is incremented by +1 each time. It is unlikely that you'd overflow 64-bit version number and risk an ABA problem, though 32-bits can be overflowed surprisingly quickly in today's computers. -------- EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). I did not mean to imply that you can "CAS any arbitrary node of a linked-list". A fully generic linked list is possible and I've seen it with the 128-bit CAS operator, but that wasn't what I was going for originally.
    - murderfs 4y ago
      > EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). No, you cannot. The problem is what you're comparing and swapping into the head during a pop. You want to do the moral equivalent of `current = list; list.compare_exchange(current, current->next)`, but current->next might have changed if someone else popped the original head, pushed something else, and then pushed the original head again. You need double CAS or LL/SC or a more complicated scheme to make this work.
elteto 4y ago
I much prefer deques to linked lists when I need O(1) push/pop but still want to keep some semblance of cache locality. Although you can't splice two deques together as easily as two linked lists. Sadly, you can't really control the block size in C++'s std::deque so you can't communicate useful information to the library about your use case. I think MSVC allocates such a small block that it is effectively a linked list.
- intrepidhero 4y ago
  How does a dequeue improve the situation with cache locality versus a linked list?
  - blibble 4y ago
    it's typically implemented as an array (e.g. circular buffer)
  - zwkrt 4y ago
    Mosty dequeues are implemented under the hood with arrays. A linked list usually requires a heap allocation for each element. This is speaking in generalities though, since you could have an “alternatively implemented dequeue or a linked list entirely on the stack.
  - klyrs 4y ago
    It depends on the implementation. Python's deque, for example, is implemented as a two-level data structure; a circularly linked list of blocks. If you've got page-sized blocks, then your deque can be sufficiently local for most cases. It introduces a little extra logic, and you'll want to keep around a spare block to prevent thrashing memory if you repeatedly push/pop at the block boundary, but it's often worth the pain if the data structure is anywhere near a hot loop.
  - Shorel 4y ago
    It is usually implemented as linked arrays. For example, arrays of 16 or 64 elements, if it grows over that size, new arrays or vectors are used underneath. Two consecutive elements are probably in the same array, and that helps with cache locality.
js2 4y ago
> Linked lists are conceptual. A node pointing to itself is the most self centered thing I can imagine in computing: an ideal representation of the more vulgar infinite loop. A node pointing to NULL is a metaphor of loneliness. A linked list with tail and head connected, a powerful symbol of a closed cycle. Tongue-in-cheek, but this really made me smile. :-)
scaramanga 4y ago
My favorite typo/brainfart so far this week has to be "cache obviousness" :)
armchairhacker 4y ago
Linked lists are great to know and understand. Linked lists are not good for performance. In most cases, an array or other data structure is much more efficient than a linked list. But there are cases where linked lists' immutability/segmentation or simplicity to implement make them the better choice.
- taeric 4y ago
  There are, interestingly, also times when fun facets of the linked lists mutability can lead to benefits. https://taeric.github.io/DancingLinks.html https://taeric.github.io/DancingLinks.html is my attempt at exploring Knuth's DLX algorithm. I can't recommend enough that you look into how he did it. Very fun and exciting use of mutable doubly linked lists.
taeric 4y ago
I suspect the problem is that many people think of stuff like Java's LinkedList when they think of linked lists. As a standard list implementation, I think it is easy to see that a doubly linked list just isn't that strong. Especially with how cumbersome the List interface makes it to take advantage of the links. That said, conceptually, linked items are everywhere; such that you can easily find how to list things following the links. You probably just don't bother keeping that in a "List" structure in your code.
- xxs 4y ago
  LinkedList is useless in Java. Aside the lock free version of them, Linked Lists are better avoided in any language (Few exceptions)
  - taeric 4y ago
    I'll forever think of this tweet when I see java's LinkeList. https://twitter.com/joshbloch/status/583813919019573248 https://twitter.com/joshbloch/status/583813919019573248 Funny, as I constantly have to tell folks to not bother using it at the office. Everyone always assumes it has to be faster than arraylist for whatever they happen to be doing this time. I think the vast majority of the time it flat doesn't matter, but I also fully expect LinkedList will lose most speed tests.
    - xxs 4y ago
      LinkedList is terrible as the memory overhead is way too high - if you need something better use an ArrayDeque.
    - smarks 4y ago
      Right. The main problem is that Java's List interface affords access by int index, making it seem array-like. Unfortunately get(i) on a LinkedList is O(n). This turns apparently innocuous things quadratic, like looping over a list by index.
      - 4y ago
forrestthewoods 4y ago
The first problem with Linked Lists is you should almost never use them. Do they have uses? Of course! However on modern computers memory access is, roughly, more expensive than CPU cycles. The Linked List has been demoted to a “special case” data structure. The second problem is Linked Lists are taught too early. They’re historically taught first in Data Structures 101. This results in new programmers using LinkedLists first when they should be used last.
readams 4y ago
Linked lists are great. But they have the problem that, almost always, whatever problem you're trying to solve would be better done with a regular resizable vector. This includes problems that they should be great for, like insert into the middle or the front. The reason is that in practice the way computers actually work is that there is an enormous time penalty for jumping around randomly in memory, and it's large enough that it's often worth paying a O(lg n) cost to switch to something that will be contiguous in memory and allow the CPU to prefetch data. There are exceptions when you really should use an actual linked list, but your default should be a vector and not a linked list.
- dmitrygr 4y ago
  Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine. Your comment would have been valid a decade or more ago. And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.
  - vbezhenar 4y ago
    RAM latency is huge. No amount of prefetching can fix that. If anything, prefetching works better with arrays as RAM reads multiple bytes at once.
  - xxs 4y ago
    Queues are best implemented with a pow2 cyclic array, and you have a free deque, too.
    - attractivechaos 4y ago
      A ring-buffer based queue is mostly better than a linked list but it is not necessarily the best. The typical STL deque implementation [1], with all its complexity, is usually faster than a ring buffer. [1] https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl https://stackoverflow.com/questions/6292332/what-really-is-a...
  - Borealid 4y ago
klntsky 4y ago
Not to mention path sharing (also called structural sharing) for free.
chrisseaton 4y ago
I've used linked lists where I wanted allocation of an almost-write-only log data structure to be very fast - so not resizing a buffer, and nobody cares about cache locality except for allocation. In a system with a TLA buffer and bump-allocation, this is absolutely ideal because allocation is local and very fast, and does not cause any of the existing log to be brought into cache. "Nobody uses this data structure stuff in real programming at work! You can forget it after college!"
- deleted 4y ago
  [deleted]
- eatonphil 4y ago
  Here's another example for the crowd: an "unbounded" fifo queue in a fixed memory environment. https://github.com/tigerbeetledb/tigerbeetle/blob/main/src/fifo.zig https://github.com/tigerbeetledb/tigerbeetle/blob/main/src/f...
jbandela1 4y ago
In my experience, the linked lists that are useful are intrusive linked lists where the data you care about has a next/previous embedded pointer as opposed to an just storing an arbitrary object inside a linked list. One example would be if your thread structure has these embedded pointers, you can easily add/remove a thread to a linked list of threads waiting for some resource without any allocation just by pointer manipulation.
- klysm 4y ago
  The other benefit of this kind of data structure is the ability for one object to participate in multiple collections. Otherwise you would have to do some kind of hash map structure to point to them.
  - kelnos 4y ago
    Isn't that the opposite, though? If you store the next/prev pointers in the data structure itself, you can't use the same object in multiple collections. If you have a standalone linked list data structure, then you can, as long as you have a good means of tracking the lifetime of the data itself.
    - nirs 4y ago
      Typically you keep a list entry in the struct: https://man7.org/linux/man-pages/man3/stailq.3.html#EXAMPLES https://man7.org/linux/man-pages/man3/stailq.3.html#EXAMPLES The same list entry can be moved between several lists using the same type. If the struct need to be in multiple lists in the same time you can keep multiple list entries in the same struct: https://github.com/freebsd/freebsd-src/blob/69413598d2660054e29cac9454fe18c08e3bf36d/sys/sys/proc.h#L237 https://github.com/freebsd/freebsd-src/blob/69413598d2660054...
- antirez 4y ago
  This is a very popolar use case inside kernels implementations.
  - 4y ago
ignoramous 4y ago
> Linked lists are simple. It is one of those rare data structures, together with binary trees and hash tables and a few more, that you can implement just from memory without likely stepping into big errors. Well, if one likes linked lists enough, they can replace binary search trees / hash tables with a skip list. Super powerful and easier to implement than splay trees, red black trees, avl trees, augmented trees, what-have-you.
ComputerGuru 4y ago
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.
- docandrew 4y ago
  When I need to avoid an allocation it's because I'm writing an allocator :) Overlaying the list nodes on top of a block of free memory avoids the need for a secondary data structure to keep track of free areas. The other time allocations are undesirable, and therefore linked lists are widely-used, is bare metal work when other allocators just aren't available. You can do tricks like representing pools of free and in-use objects with two lists where the nodes occupy the same memory block. Allocations are a fast O(1) unlink from the free list and O(1) re-link to the used list, and frees are the opposite.
photochemsyn 4y ago
For educational purposes (i.e. hooking easily into graphics packages for visualization) you can make a linked list in Python, using elements like: class Node: def __init__(self, dataval=None): self.dataval = dataval self.nodepointer = None The only reason to do this is for education/visualization of data structures, although I'm wondering if this can be engineered to cause a Python memory leak, via circularization of the linked list, or if Python's GC would catch it. Also educational perhaps. Where linked lists really seem to come into play is with custom manual memory allocators in embedded programming, something of a niche subject.
- NavinF 4y ago
  > I'm wondering if this can be engineered to cause a Python memory leak, via circularization of the linked list Not unless you manually disable gc. https://docs.python.org/3/library/gc.html https://docs.python.org/3/library/gc.html "Since the collector supplements the reference counting already used in Python, you can disable the collector if you are sure your program does not create reference cycles"
btilly 4y ago
In scripting languages it is a truism that anything you would want to do with a linked list is probably better done with an array. And given the overhead of working in the language versus things implemented in C, this is generally true. However I have a fun use for linked lists where this is NOT true. Anyone who has played around with algorithms has encountered dynamic programming. So you can, for example, find the count of subsets that sum to a particular number without actually enumerating them all. But what if instead of counting them, you wanted to actually find some? The answer turns out to be that instead of using dynamic programming to get a count, you use dynamic programming to build up a data structure from which you can get the answer. And the right data structure to use turns out to be...a type of linked list! There is no faster array equivalent for what you get. In other words, with a few extra fields for clarity, here is the basic structure for subset sum of positive integers: { current_sum: ..., count_of_solutions: ..., current_value: ..., solutions_using_current_value: (link in one dim of linked list), solutions_using_previous_values: (link on other dim of linked list), } I leave figuring out the dynamic programming code to generate this as a fun exercise. Likewise how to extract, say, the 500'th subset with this sum. Both are easy if you understand linked lists. If not...well...consider it education!
- wwweston 4y ago
  Suspicion: this is because a positive integer is a linked list. Every integer is defined by a unary root element and then a series of successors until its cardinality matches the corresponding symbol (counting is correspondence). > find the count of subsets that sum to a particular number without actually enumerating them all. Would the generating formula for partition numbers[0] work, or am I misunderstanding this problem? (I think actually generating the subsets is necessarily a dynamic programming problem...) [0] https://en.wikipedia.org/wiki/Partition_(number_theory)#:~:text=the%20generating%20function%20formula%20described%20below%3A https://en.wikipedia.org/wiki/Partition_(number_theory)#:~:t...
  - btilly 4y ago
    You are misunderstanding the problem. Given a particular set, the question is enumerating the subsets that add to a particular thing. The fact that numbers themselves could be represented as a linked list has nothing to do with it. And there is no particularly useful generating function to use either. For example there are 303 primes less than 2000, and 47,839,398,752,301 subsets of them add up to 2000. If you arrange them in lexicographic order, what is the 5 trillionth one?
adeptima 4y ago
When people asking my opinion for Rust, I loved to share them the Linkedin List implementation link: https://doc.rust-lang.org/src/alloc/collections/linked_list.rs.html#158 https://doc.rust-lang.org/src/alloc/collections/linked_list.... And the first feedback is why so many unsafe blocks? What is it Option<NonNull<Node<T>>> ? '_ ? Another reason to share, if you can understand Linkedin List, you are free to code in Rust ;)
- SighMagi 4y ago
  There’s so much code marked “unsafe” in there…
  - tracker1 4y ago
    There be dragons...
  - estebank 4y ago
    That's because in order to interact with pointers you need unsafe, and not using unsafe in Rust requires a single ownership tree or reference counting. If you're not keen on either of those solutions, you shouldn't be writing a Doubly Linked List in other languages either (because they will have either pointers or reference counting/GC).
    - andrewflnr 4y ago
      "Those solutions" start off being hierarchical ownership or reference counting, but turn into "pointers or reference counting". Requiring pointers is implicit to the definition of linked lists, and calling it out here is silly. And you don't really need either ref counting (again, pretty obviously, witness every real world implementation) or hierarchical ownership outside Rust. Conceptually, the list as a vague concept owns all the nodes. The ownership just stops being expressible directly through references the way Rust wants it to be. But you don't have to re-invent hierarchical ownership to implement DLLs in other languages, because it's not really there in the problem. You just have to accept that they're always going to suck under Rust's ownership model.
ayhanfuat 4y ago
For completenes, here’s what Bjarne Stroustrup says on why you should avoid using linked lists: https://youtu.be/YQs6IC-vgmo https://youtu.be/YQs6IC-vgmo
- db48x 4y ago
  This is a video everyone should watch.
c-smile 4y ago
Why do we need to defend a hammer against a sickle? Each tool has its own value it was designed for ... Try to imagine LISP without lists ...
- klysm 4y ago
  A list can have different memory representations with identical semantics.
- bsder 4y ago
  > Try to imagine LISP without lists ... It's called Clojure. Getting rid of CONS (effectively removing singly linked lists) is a huge benefit.
tunesmith 4y ago
How do you detect a cycle with linked lists? :) I actually have a side project where I've run into this - it's a distributed directed graph structure where the nodes can send messages to each other. It's intended to be acyclic, but "walking the graph" is really only used to send truth values, which are combined with others to run Boolean logic. So in that case, the occasional cycle doesn't matter, because if the calculated boolean value matches that of the node's internal state, it just can cease propagating. So a structural loop won't turn into an infinite processing loop. The problem then becomes that I can't introduce NOT gates anywhere in a cycle, because then the bit will continue flipping and I'll get an infinite processing loop. So it seems my only hope is external processes that continually walk the graph and keep track of where it visited to try and detect loops, and I don't like how that scales...
- bewaretheirs 4y ago
  Set two pointers to the head of the list. Step through the list by one element per iteration with one of them, and with the other, step every other iteration. If the two pointers are ever again equal you've found a cycle. If you hit end of list, no cycle.
- klysm 4y ago
  Does the graph have static structure? I’m not sure if you’re describing something like an actor system.
  - tunesmith 4y ago
    Akka cluster sharding :) Shape of the graph can change as processes are being run.
- dragontamer 4y ago
  With "just" a linked list, you need a turtle (advance one-node at a time), and a hare (advance two-nodes at a time). If the turtle and hare ever meet, you have a cycle. Otherwise, if the hare reaches the end of the list, you don't have a cycle.
waynecochran 4y ago
Another cool property about linked lists is that you can add an element to the head of a list without mutating the previous list. There are not many data structure that you can add an element to and leave the previous version unchanged. This form of immutability is a very nice feature that Lisp / functional programmers enjoy. Because of this, you can concurrently add an element to the head of a list to create new lists without having a critical section in your code.
- robocat 4y ago
  > you can concurrently add an element to the head of a list to create new lists without having a critical section The race is on: now you have two lists when before you had one?
  - rileyphone 4y ago
    Every element of the list, from its own point of view, is another list.
lanstin 4y ago
I just used linked lists to make an LRU hard limit on the number of items in an in memory store. Each usage, the pointers are updated to move the item to the head. Each time the list is at the limit, the tail is removed and freed. I may take advantage of the machinery to make it go onto free list. This was Go and the DLL thing is my first use of generics.
layer8 4y ago
I think I first learned about linked lists in the context of programming for AmigaOS, which has a standardized form of (intrusive) linked lists that is used throughout the system. I remember being fascinated by the header node which serves as both the head and the tail of a list due to a “clever” field layout: https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues
- Narishma 4y ago
  Linked lists made more sense back then when memory access wasn't as slow compared to CPU speed.
deleted 4y ago
[deleted]
scottlamb 4y ago
> 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.
- pornel 4y ago
  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.
  - scottlamb 4y ago
    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 https://wiki.postgresql.org/wiki/Fsync_Errors
  - colonwqbang 4y ago
    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.
stephc_int13 4y ago
The good thing about linked list is how easy they are to understand and use, almost trivial. The bad thing is that their cost nis ot obvious and not consistent (difficult to predict). I tend prefer simple arrays. This talk by Mike Acton is a good introduction to understand why going for the linked list as go-to data structure can lead to performance issues. https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
koinedad 4y ago
They are really cool. Deleting an element by assigning next to next.next still blows my mind.
- Jtsummers 4y ago
  If you think that's neat, check out Dancing Links used for backtracking algorithms: https://en.wikipedia.org/wiki/Dancing_Links https://en.wikipedia.org/wiki/Dancing_Links
bitwize 4y ago
Linked lists are one of those things, like textual protocols, that people reach for because they're easy and fun but, from an engineering standpoint, you should never, ever use unless you can provide a STRONG justification for doing so. The locality of reference characteristics of vectors mean that, except for extreme cases, they beat linked lists almost every time on modern cached CPUs.
Jtsummers 4y ago
Language wars, editor wars, and now data structure wars. What random technical thing will people go to virtual blows over next?
- keepquestioning 4y ago
  https://www.reddit.com/r/slatestarcodex/comments/9rvroo/most_of_what_you_read_on_the_internet_is_written/ https://www.reddit.com/r/slatestarcodex/comments/9rvroo/most...
  - B1FF_PSUVM 4y ago
    I'd note that the number of people creating content now is probably two or six orders orders of magnitude larger than before the internet, when it was just print/radio/TV/etc. Most that Joe Random could expect to get in print would be a Letter to the Editor, or a random passerby interview. The in-crowd was even more "unusual".
AtNightWeCode 4y ago
People must stop give attention to old garbage solutions that should not be used. Never use a link list if you don’t specifically need a link list. You probably don’t know why you would need one so don’t go there.
- tester756 4y ago
  It could be way better advice if you tried
- int_19h 4y ago
  If you stop "giving attention" to old solutions, people will simply reinvent them. Linked lists in particular are very easy to reinvent because they're so simple, and because their advantages are all evident even in a high-level language, while disadvantages require a more low-level understanding of modern compute performance.
belter 4y ago
“Does anyone use LinkedList? I wrote it, and I never use it.” - https://news.ycombinator.com/item?id=33418705 https://news.ycombinator.com/item?id=33418705
- int_19h 4y ago
  "Don't get me wrong; I love linked lists. They're as useful in C as they are in Scheme. But LinkedList is another matter entirely."
thedracle 4y ago
There was a time when memory was conventionally expensive, memory allocation of large blocks was slow, and small blocks was much faster (malloc would find a small block faster than a large one on a highly fragmented heap). Before having gigantic caches that would engulf nearly any sized contiguous list, linked lists were sort of vogue, frugal, and thought of as being fairly performant.
- AstralStorm 4y ago
  That time is still there in embedded hardware. Even potent ARM chips (except the cellphone ones maybe) have some KB of cache at best, and similar amounts of SRAM. While code size is still at a premium since XIP (execute-in-place from in-built flash) is slower.
nialv7 4y ago
It's odd that the author states they wrote the article in response to arguments on Twitter, yet they didn't show us the arguments this was a response to.
dreamcompiler 4y ago
Lisp of course was originally invented for manipulating linked lists and it came about in an era where cache locality wasn't an issue because computers in 1959 were speed limited by their CPUs rather than their memories. Cdr coding [0] solves several problems with singly-linked (cons-style) lists including cache locality and the 2x storage overhead of these lists. But it's not typically used except in dedicated hardware e.g. Lisp machines. It could in principle be revived fairly easily on modern 64-bit Lisp systems on stock hardware -- especially if such systems provided immutable cons cells. But it's probably not worthwhile because modern Lisp programmers (in Common Lisp at least) don't use lists all that much. CL has very nice adjustable arrays and hash tables that are easier and faster than lists for most purposes. [0] https://en.m.wikipedia.org/wiki/CDR_coding https://en.m.wikipedia.org/wiki/CDR_coding
ww520 4y ago
Linked list is useful when you are hurting for memory and need precision memory allocation, like in the kernel. You trade memory compactness for more operation time in dealing with its certain aspects.
- AstralStorm 4y ago
  And code size, let's not forget about that one. Plus you do not have a super smart memory allocator to prevent the hundreds of vectors from spraying the heap.
gslepak 4y ago
Anyone else getting a serious cert expired warning when visiting this site? The one I'm getting is also for the wrong name - registered for redis.io and expired on `Fri, 07 Aug 2020 11:30:03 GMT`. Issued by Let's Encrypt. Fingerprint: `07:BF:EA:59:DB:83:33:77:50:27:A8:C5:2F:80:F6:CA:E6:EC:E2:7D:01:DB:72:7A:AF:EE:69:DD:EC:2D:DA:F3` Seems like a MITM attack is going on.
- gslepak 4y ago
  Oh, nevermind, link was submitted in HTTP, but I have mandatory HTTPS enabled and the server is misconfigured.
m3kw9 4y ago
If you work on iOS, it’s really hard to do a better job than what the SDK has implemented in the arrays function.
cbreynoldson 4y ago
> You get what data structures made of links truly are: the triviality of a single node that becomes a lot more powerful and complex once it references another one. I don't think beginners actually make this connection for a while. Linked Lists are introduced analogously to arrays, sets, etc. Beginners think about Linked Lists in terms of what they already know. As a beginner, I thought of Linked Lists purely as non-contiguous arrays, even though there are deeper concepts behind them. Unless the beginners already have the perspective of "same having the power as the whole", I don't think this connection gets made for a while. Linked Lists don't expose so much possibility on their own.
fortran77 4y ago
I think the Rust people are de-emphasizing the importance of linked lists due to the glaring hole in the Rust language that makes it difficult to implement linked lists, and horribly awkward to do doubly-linked lists in safe Rust (See https://rcoh.me/posts/rust-linked-list-basically-impossible/ https://rcoh.me/posts/rust-linked-list-basically-impossible/ ) To save face, the Rust astroturfers are now skipping around saying "Linked lists aren't important"
- c-cube 4y ago
  The author is a known C programmer (he wrote redis). You're imagining things.
  - fortran77 4y ago
    Yes; sorry I wasn't clear. I meant the people on HN commenting on "In defense of linked lists"
lacrosse_tannin 4y ago
Linked lists don't care about you. They aren't even alive.
- TheDudeMan 4y ago
  Is that a "pro" or a "con"?
Legion 4y ago
> (oh, dear Twitter: whatever happens I’ll be there as long as possible – if you care about people that put a lot of energy in creating it, think twice before leaving the platform) You mean the people that all just got fired?
javajosh 4y ago
Linked lists are cool, but he missed one reason why: how easily they become n-arry trees. A tree expressed like this is quite elegant and useful in a variety of domains, my favorite being a "trie" that is an n-arry tree that computes the label of each node as the string you get from the previous label plus the string in this node. It's a wild and hairy data-structure, but very cool once tamed.
sytelus 4y ago
Linked lists don’t need defense. It is unfortunate that job of vast majority of developers is rather benign. They don’t work on problems that requires complex algorithms and data structures beyond arrays and dictionaries. But interviewers keep asking those questions and give bad rep to these subjects. However, if you are working on building any real infrastructures such as search, deep learning, cloud, crypto, game engines, OS, compilers etc then you need linked lists, graphs, trees and myriad of algorithms surrounding them all the time. There is clearly different tier of developers who work on such infrastructure and those you simply utilize infrastructures others have built.
grog454 4y ago
There is no contiguous memory, arbitrarily resizeable alternative to a linked list in high performance concurrency is there? https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html https://docs.oracle.com/javase/7/docs/api/java/util/concurre...
deleted 4y ago
[deleted]
zebb 4y ago
> In defense of linked lists In defense of what? A brigade of null pointer exceptions? > Linked lists are conceptual. A node pointing to itself is the most self centered thing I can imagine in computing: an ideal representation of the more vulgar infinite loop. A node pointing to NULL is a metaphor of loneliness. A linked list with tail and head connected, a powerful symbol of a closed cycle. Oh, this article is complete satire. Bravo, you had me
subarctic 4y ago
Interesting, I have to disable HTTPS Everywhere on this site, otherwise it redirects me to https://redis.io/news/138 https://redis.io/news/138 and I get a 404 page.
raible 4y ago
FWIW I usefully use a "fake" linked list by adding a .next field to the struct in a compiler-allocated array of structs. On initialization I set the list head to &item[0], and in a trivial loop set the .next field of each entry (except the last) to entry+1. Why bother? Because I can then easily add a few extra structs to the beginning of the (contiguously-allocated) linked-list without having to reallocate the whole thing. Sure, pointer chasing with separately allocated structs is "slow", but I haven't yet measured to see if it's any different when (almost all) items are contiguous. If you would... - what sort of cache behavior should one expect of this on a modern laptop CPU? - I haven't seen this approach before, have you?
- Sirened 4y ago
  It depends on what prefetchers your CPU has and the actual underlying access pattern your accesses cause. If chasing next leads to a constant stride run through the array, you'll get identical performance to that of an iterative walk since essentially every high performance CPU since like 2010 supports stride prediction based on raw addresses. If .next sends you bouncing all over the area, you'll get complicated behavior since whether or not the data can be prefetched depends on the performance/existence of a pointer prefetcher, which is less common/more error prone. We know Apple's M1 have it due to some researchers using it as a side channel [1] but you'll have to do some digging on whether or not your laptop has one. Would make a nice post here if you do make the benchmarks :) [1] https://www.prefetchers.info/augury.pdf https://www.prefetchers.info/augury.pdf
  - raible 4y ago
    Thanks for that, it's what I had hoped for (but again, have not yet measured). It seems to me it's a super-handy way of "modifying" a compiler-allocated array of structs. I'm sticking with it!
pugworthy 4y ago
Linked lists are great. But they have the problem that, almost always, whatever technical interview you have, someone asks you to whiteboard how to reverse one. And I answer, "I'd google it"
summerlight 4y ago
https://twitter.com/cpuGoogle/status/1415061974820421635 https://twitter.com/cpuGoogle/status/1415061974820421635 A nice explanation on rationales of using linked lists in OS kernel, from a Fuchsia developer. In short, it is almost guaranteed not to fail on most typical operations given the invariant is not broken, which make it suitable for cases where there's no fallback option left like kernel codes.
sudarshnachakra 4y ago
I guess linked lists as they are are very useful for implementing queues (particularly those that feed thread pools) where-in the costs of growable array is not needed and the cache locality does not matter (continuing with a thread pool example - It's almost a guarantee that having next element in the cache of the CPU which is not going to execute the next Runnable is a waste). In Java particularly the both array as well as the linked implementation of blocking queues should perform equally well. FWIW most queue implementations are linked lists.
- NavinF 4y ago
  The best implementations typically have a queue per thread and work stealing. The first threads to finish their assigned work will grab items from other queues, but until then you get perfect cache locality. Java's queues and global threadpool queues in general are pretty old hat.
DeathArrow 4y ago
While there's a certain use for linked lists - in operating systems kernels for example and as a programmer you absolutely have to know how linked lists work, there are other linear data structures which are more suited for general programming. To give a C# example, arrays, lists and dictionaries (hash tables) implement iterators so you can always know what the next element in collection is. Elements can be accessed by key or index in O(1),elements can be added in O(1). The case in which you absolutely have to insert an element in a particular position is rare so linked lists are seldom used. The same case is for C++, there is a vector class in STL but no linked list class. Same for Java.
- selimco 4y ago
  > The same case is for C++, there is a vector class in STL but no linked list class. Same for Java. Java does have a linked list in the standard library: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedList.html https://docs.oracle.com/en/java/javase/17/docs/api/java.base...
- cyber_kinetist 4y ago
  > The same case is for C++, there is a vector class in STL but no linked list class. No, there is std::list. https://en.cppreference.com/w/cpp/container/list https://en.cppreference.com/w/cpp/container/list > Same for Java. Also no, LinkedList exists. https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html https://docs.oracle.com/javase/7/docs/api/java/util/LinkedLi...
cyber_kinetist 4y ago
I think the whole "dynamic arrays" vs "linked lists" debacle is just a waste of time, since the two actually complement each other. - You can certainly implement linked lists using dynamic arrays, so you call the minimal amount of `malloc()`s and also make your items stored contiguously! You need to use indices instead of pointers, since you will lose pointer stability unless you use virtual memory (though the upside is that typically a uint32_t is enough for most cases, which only takes up half as much memory as a pointer). - A lot of data structures under the hood uses linked lists, even the ones that seem to use dynamic arrays on the surface. Have experience in writing a simple arena allocator? For the allocator to find a free space in the arena in O(1), you need to maintain a free-list data structure under the hood. And guess what: you need to write a linked list. Even your operating systems' `malloc()` itself probably uses linked lists under the hood. - Linked lists just come up inside so many other data structures, that you can essentially call it as the 'backbone'. For example: in compute graphics there is something called a half-edge data structure [0], which stores the geometry data of a mesh that's both compact, easy to iterate, and easy to do manipulations with (for instance, you can do things like insert/delete an edge/face easily in O(1) time, and more complex mesh operations can be implemented as well). And guess what? The vertices and halfedges are essentially stored in a complex web of linked lists. [0] https://jerryyin.info/geometry-processing-algorithms/half-edge/ https://jerryyin.info/geometry-processing-algorithms/half-ed...
Razengan 4y ago
Seems to me that all these arguments are rooted in the way computer memory is fundamentally implemented: Could it not be possible to re-architecture it so that it's more agreeable to arrays and lists, since that's how most data is used? I often wonder about the separation of CPU and RAM, of ways it could be done better. How about making it like neurons, where each "memory cell" is also a teeny tiny computer itself? (How DO neurons do internal computation anyway?)
deafpolygon 4y ago
Honestly, a lot of programming data structure concepts were difficult to grasp /until/ I truly understood how linked list works. It's a very simple concept in hindsight, but as a newbie programmer - this was an alien concept. Linked list? Just give me my array or built in List! Then I understood how to build a linked list and how it can be extended in various ways. They can be used to solve interesting problems. Many high level languages provide pre-baked implementations of LL but most programmers don't understand how they work under the surface. When I understood LL, I was able to apply that understanding to trees.
tomcam 4y ago
> Linked lists are simple. It is one of those rare data structures, together with binary trees and hash tables and a few more, that you can implement just from memory without likely stepping into big errors. One of the best engineers in Microsoft’s devdiv told me that he often gave a linked list implementation in C as a whiteboard assignment for interviewees and that no one ever managed a bug-free version. (I failed mine even after creating a full general purpose implementation on my own just a couple years before.)
- antirez 4y ago
  One thing is: you have 30 minutes of time and can compile and test and end with a working implementation. Another thing is write the code on a whiteboard, that is a process nobody ever follows in practice: very easy to make mistakes this way. Anyway doubly linked lists are easy to get wrong without compiling / testing.
pharmakom 4y ago
Immutable linked lists are a cornerstone of functional programming. However, Clojure has shown that the underlying implementation if often better done using a tree of contiguous memory blocks.
ordiel 4y ago
For an "article" starting with a ramble about how the author's life is being tragically affected by "the fate of Twitter", the sentence > get ready to read a sentimental post about a data structure Makes a looot of sense
sprawld 4y ago
Donald Knuth's Dancing Links paper is a beautiful exploration of the power of linked lists. He uses a table with doubly linked lists (for rows and cols) to solve omino tiling. The linked lists allow for an elegant unpicking of rows (and re-attaching when backtracking) The paper's a really enjoyable read, Knuth's tone throughout is "look at this, this is fun" https://arxiv.org/abs/cs/0011047 https://arxiv.org/abs/cs/0011047
- deleted 4y ago
  [deleted]
GnarfGnarf 4y ago
I have built my business on linked lists (genealogy trees). Paid for my house :o)
OOPMan 4y ago
Oh lord, can anyone make a post without whining on about Twitter?
fnordpiglet 4y ago
Linked lists also work great in a sharded distributed data structure. You can make changes to the list structure by simply changing reference at nodes and don’t need to move anything.
visarga 4y ago
That was my high school programming fun - implement linked lists and other data structures in TurboPascal. Pascal is a language that does not come with dynamic lists, only fixed size arrays and memory allocations. I had to build linked lists just to have a decent list primitive. A few years later I discovered Perl that comes with dynamic size lists, dictionaries and strings. Whoa, that was a treat, so very nice to use and efficient. To this day I prefer constructs made of lists and dicts 10x more than defining classes.
TurkishPoptart 4y ago
Can someone post an example of a linked list? I don't really understand this article.

603 points by grep_it 4y ago

I think this article could be more intelligently titled: "Don't post, read, or respond to things on TWTR". The linked lists aspect could be replaced with anything.

TillE 4y ago

The Windows kernel also has linked lists as one of its few general-purpose data structures available to drivers. Like any tool, it has its place. As long as you're not traversing large linked lists, they're probably fine.

dilyevsky 4y ago
Traversing a short list but frequently still going to have terrible cache performance compared to something like vector. Just use vectors, folks
- deleted 4y ago
  [deleted]
- slaymaker1907 4y ago
  Allocating a huge chunk of memory all at once when the array grows can also cause a bunch of problems. Linked lists are also much simpler in a multi threaded context.
  - dilyevsky 4y ago
    I’m not an expert in memory allocators but I suspect large allocation is better than many small allocs due to less fragmentation no? I’ll grant you the multithreaded case but if you’re doing that your cache performance is probably crap anyway =)

dragontamer 4y ago

The most interesting thing about linked lists to me is how trivially it can be made lock-free multithreaded with atomics. An array/stack can be made multithreaded but it is non-trivial to handle the edge-cases. In particular, the ABA problem is rather difficult. I've seen many solutions to it (ex: a synchronization variable that puts the stack into "push-only" mode and then "pop-only" mode. There's no ABA-problem if all threads are pushing!) However, pushing/popping from a Linked List stack requires no such synchronization at all. Simply compare-and-swap the head (and on failure, try again). Its about as simple as you can get when it comes to atomic / lock free patterns.

yeputons 4y ago
> Simply compare-and-swap the head (and on failure, try again). It doesn't help with ABA at all, does it? Unless you assume that nodes are immutable and the same pointer is never reused, of course.
- dragontamer 4y ago
  I forgot about that other ABA issue. Still, that's easily solved: 64-bit version number + 64-bit pointer (or 32-bit version number + 32-bit pointer) for a 128-bit (or 64-bit) compare-and-swap. All modern CPUs support 128-bit CAS. EDIT: The version number is incremented by +1 each time. It is unlikely that you'd overflow 64-bit version number and risk an ABA problem, though 32-bits can be overflowed surprisingly quickly in today's computers. -------- EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). I did not mean to imply that you can "CAS any arbitrary node of a linked-list". A fully generic linked list is possible and I've seen it with the 128-bit CAS operator, but that wasn't what I was going for originally.
  - murderfs 4y ago
    > EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). No, you cannot. The problem is what you're comparing and swapping into the head during a pop. You want to do the moral equivalent of `current = list; list.compare_exchange(current, current->next)`, but current->next might have changed if someone else popped the original head, pushed something else, and then pushed the original head again. You need double CAS or LL/SC or a more complicated scheme to make this work.

elteto 4y ago

I much prefer deques to linked lists when I need O(1) push/pop but still want to keep some semblance of cache locality. Although you can't splice two deques together as easily as two linked lists. Sadly, you can't really control the block size in C++'s std::deque so you can't communicate useful information to the library about your use case. I think MSVC allocates such a small block that it is effectively a linked list.

intrepidhero 4y ago
How does a dequeue improve the situation with cache locality versus a linked list?
- blibble 4y ago
  it's typically implemented as an array (e.g. circular buffer)
- zwkrt 4y ago
  Mosty dequeues are implemented under the hood with arrays. A linked list usually requires a heap allocation for each element. This is speaking in generalities though, since you could have an “alternatively implemented dequeue or a linked list entirely on the stack.
- klyrs 4y ago
  It depends on the implementation. Python's deque, for example, is implemented as a two-level data structure; a circularly linked list of blocks. If you've got page-sized blocks, then your deque can be sufficiently local for most cases. It introduces a little extra logic, and you'll want to keep around a spare block to prevent thrashing memory if you repeatedly push/pop at the block boundary, but it's often worth the pain if the data structure is anywhere near a hot loop.
- Shorel 4y ago
  It is usually implemented as linked arrays. For example, arrays of 16 or 64 elements, if it grows over that size, new arrays or vectors are used underneath. Two consecutive elements are probably in the same array, and that helps with cache locality.

js2 4y ago

> Linked lists are conceptual. A node pointing to itself is the most self centered thing I can imagine in computing: an ideal representation of the more vulgar infinite loop. A node pointing to NULL is a metaphor of loneliness. A linked list with tail and head connected, a powerful symbol of a closed cycle. Tongue-in-cheek, but this really made me smile. :-)

scaramanga 4y ago

My favorite typo/brainfart so far this week has to be "cache obviousness" :)

armchairhacker 4y ago

Linked lists are great to know and understand. Linked lists are not good for performance. In most cases, an array or other data structure is much more efficient than a linked list. But there are cases where linked lists' immutability/segmentation or simplicity to implement make them the better choice.

taeric 4y ago
There are, interestingly, also times when fun facets of the linked lists mutability can lead to benefits. https://taeric.github.io/DancingLinks.html https://taeric.github.io/DancingLinks.html is my attempt at exploring Knuth's DLX algorithm. I can't recommend enough that you look into how he did it. Very fun and exciting use of mutable doubly linked lists.

taeric 4y ago

I suspect the problem is that many people think of stuff like Java's LinkedList when they think of linked lists. As a standard list implementation, I think it is easy to see that a doubly linked list just isn't that strong. Especially with how cumbersome the List interface makes it to take advantage of the links. That said, conceptually, linked items are everywhere; such that you can easily find how to list things following the links. You probably just don't bother keeping that in a "List" structure in your code.

xxs 4y ago
LinkedList is useless in Java. Aside the lock free version of them, Linked Lists are better avoided in any language (Few exceptions)
- taeric 4y ago
  I'll forever think of this tweet when I see java's LinkeList. https://twitter.com/joshbloch/status/583813919019573248 https://twitter.com/joshbloch/status/583813919019573248 Funny, as I constantly have to tell folks to not bother using it at the office. Everyone always assumes it has to be faster than arraylist for whatever they happen to be doing this time. I think the vast majority of the time it flat doesn't matter, but I also fully expect LinkedList will lose most speed tests.
  - xxs 4y ago
    LinkedList is terrible as the memory overhead is way too high - if you need something better use an ArrayDeque.
  - smarks 4y ago
    Right. The main problem is that Java's List interface affords access by int index, making it seem array-like. Unfortunately get(i) on a LinkedList is O(n). This turns apparently innocuous things quadratic, like looping over a list by index.
    - 4y ago

forrestthewoods 4y ago

The first problem with Linked Lists is you should almost never use them. Do they have uses? Of course! However on modern computers memory access is, roughly, more expensive than CPU cycles. The Linked List has been demoted to a “special case” data structure. The second problem is Linked Lists are taught too early. They’re historically taught first in Data Structures 101. This results in new programmers using LinkedLists first when they should be used last.

readams 4y ago

Linked lists are great. But they have the problem that, almost always, whatever problem you're trying to solve would be better done with a regular resizable vector. This includes problems that they should be great for, like insert into the middle or the front. The reason is that in practice the way computers actually work is that there is an enormous time penalty for jumping around randomly in memory, and it's large enough that it's often worth paying a O(lg n) cost to switch to something that will be contiguous in memory and allow the CPU to prefetch data. There are exceptions when you really should use an actual linked list, but your default should be a vector and not a linked list.

dmitrygr 4y ago
Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine. Your comment would have been valid a decade or more ago. And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.
- vbezhenar 4y ago
  RAM latency is huge. No amount of prefetching can fix that. If anything, prefetching works better with arrays as RAM reads multiple bytes at once.
- xxs 4y ago
  Queues are best implemented with a pow2 cyclic array, and you have a free deque, too.
  - attractivechaos 4y ago
    A ring-buffer based queue is mostly better than a linked list but it is not necessarily the best. The typical STL deque implementation [1], with all its complexity, is usually faster than a ring buffer. [1] https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl https://stackoverflow.com/questions/6292332/what-really-is-a...
- Borealid 4y ago

klntsky 4y ago

Not to mention path sharing (also called structural sharing) for free.

chrisseaton 4y ago

I've used linked lists where I wanted allocation of an almost-write-only log data structure to be very fast - so not resizing a buffer, and nobody cares about cache locality except for allocation. In a system with a TLA buffer and bump-allocation, this is absolutely ideal because allocation is local and very fast, and does not cause any of the existing log to be brought into cache. "Nobody uses this data structure stuff in real programming at work! You can forget it after college!"

deleted 4y ago
[deleted]
eatonphil 4y ago
Here's another example for the crowd: an "unbounded" fifo queue in a fixed memory environment. https://github.com/tigerbeetledb/tigerbeetle/blob/main/src/fifo.zig https://github.com/tigerbeetledb/tigerbeetle/blob/main/src/f...

jbandela1 4y ago

In my experience, the linked lists that are useful are intrusive linked lists where the data you care about has a next/previous embedded pointer as opposed to an just storing an arbitrary object inside a linked list. One example would be if your thread structure has these embedded pointers, you can easily add/remove a thread to a linked list of threads waiting for some resource without any allocation just by pointer manipulation.

klysm 4y ago
The other benefit of this kind of data structure is the ability for one object to participate in multiple collections. Otherwise you would have to do some kind of hash map structure to point to them.
- kelnos 4y ago
  Isn't that the opposite, though? If you store the next/prev pointers in the data structure itself, you can't use the same object in multiple collections. If you have a standalone linked list data structure, then you can, as long as you have a good means of tracking the lifetime of the data itself.
  - nirs 4y ago
    Typically you keep a list entry in the struct: https://man7.org/linux/man-pages/man3/stailq.3.html#EXAMPLES https://man7.org/linux/man-pages/man3/stailq.3.html#EXAMPLES The same list entry can be moved between several lists using the same type. If the struct need to be in multiple lists in the same time you can keep multiple list entries in the same struct: https://github.com/freebsd/freebsd-src/blob/69413598d2660054e29cac9454fe18c08e3bf36d/sys/sys/proc.h#L237 https://github.com/freebsd/freebsd-src/blob/69413598d2660054...
antirez 4y ago
This is a very popolar use case inside kernels implementations.
- 4y ago

ignoramous 4y ago

> Linked lists are simple. It is one of those rare data structures, together with binary trees and hash tables and a few more, that you can implement just from memory without likely stepping into big errors. Well, if one likes linked lists enough, they can replace binary search trees / hash tables with a skip list. Super powerful and easier to implement than splay trees, red black trees, avl trees, augmented trees, what-have-you.

ComputerGuru 4y ago

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.

docandrew 4y ago
When I need to avoid an allocation it's because I'm writing an allocator :) Overlaying the list nodes on top of a block of free memory avoids the need for a secondary data structure to keep track of free areas. The other time allocations are undesirable, and therefore linked lists are widely-used, is bare metal work when other allocators just aren't available. You can do tricks like representing pools of free and in-use objects with two lists where the nodes occupy the same memory block. Allocations are a fast O(1) unlink from the free list and O(1) re-link to the used list, and frees are the opposite.

photochemsyn 4y ago

For educational purposes (i.e. hooking easily into graphics packages for visualization) you can make a linked list in Python, using elements like: class Node: def __init__(self, dataval=None): self.dataval = dataval self.nodepointer = None The only reason to do this is for education/visualization of data structures, although I'm wondering if this can be engineered to cause a Python memory leak, via circularization of the linked list, or if Python's GC would catch it. Also educational perhaps. Where linked lists really seem to come into play is with custom manual memory allocators in embedded programming, something of a niche subject.

NavinF 4y ago
> I'm wondering if this can be engineered to cause a Python memory leak, via circularization of the linked list Not unless you manually disable gc. https://docs.python.org/3/library/gc.html https://docs.python.org/3/library/gc.html "Since the collector supplements the reference counting already used in Python, you can disable the collector if you are sure your program does not create reference cycles"

btilly 4y ago

In scripting languages it is a truism that anything you would want to do with a linked list is probably better done with an array. And given the overhead of working in the language versus things implemented in C, this is generally true. However I have a fun use for linked lists where this is NOT true. Anyone who has played around with algorithms has encountered dynamic programming. So you can, for example, find the count of subsets that sum to a particular number without actually enumerating them all. But what if instead of counting them, you wanted to actually find some? The answer turns out to be that instead of using dynamic programming to get a count, you use dynamic programming to build up a data structure from which you can get the answer. And the right data structure to use turns out to be...a type of linked list! There is no faster array equivalent for what you get. In other words, with a few extra fields for clarity, here is the basic structure for subset sum of positive integers: { current_sum: ..., count_of_solutions: ..., current_value: ..., solutions_using_current_value: (link in one dim of linked list), solutions_using_previous_values: (link on other dim of linked list), } I leave figuring out the dynamic programming code to generate this as a fun exercise. Likewise how to extract, say, the 500'th subset with this sum. Both are easy if you understand linked lists. If not...well...consider it education!

wwweston 4y ago
Suspicion: this is because a positive integer is a linked list. Every integer is defined by a unary root element and then a series of successors until its cardinality matches the corresponding symbol (counting is correspondence). > find the count of subsets that sum to a particular number without actually enumerating them all. Would the generating formula for partition numbers[0] work, or am I misunderstanding this problem? (I think actually generating the subsets is necessarily a dynamic programming problem...) [0] https://en.wikipedia.org/wiki/Partition_(number_theory)#:~:text=the%20generating%20function%20formula%20described%20below%3A https://en.wikipedia.org/wiki/Partition_(number_theory)#:~:t...
- btilly 4y ago
  You are misunderstanding the problem. Given a particular set, the question is enumerating the subsets that add to a particular thing. The fact that numbers themselves could be represented as a linked list has nothing to do with it. And there is no particularly useful generating function to use either. For example there are 303 primes less than 2000, and 47,839,398,752,301 subsets of them add up to 2000. If you arrange them in lexicographic order, what is the 5 trillionth one?

adeptima 4y ago

When people asking my opinion for Rust, I loved to share them the Linkedin List implementation link: https://doc.rust-lang.org/src/alloc/collections/linked_list.rs.html#158 https://doc.rust-lang.org/src/alloc/collections/linked_list.... And the first feedback is why so many unsafe blocks? What is it Option<NonNull<Node<T>>> ? '_ ? Another reason to share, if you can understand Linkedin List, you are free to code in Rust ;)

SighMagi 4y ago
There’s so much code marked “unsafe” in there…
- tracker1 4y ago
  There be dragons...
- estebank 4y ago
  That's because in order to interact with pointers you need unsafe, and not using unsafe in Rust requires a single ownership tree or reference counting. If you're not keen on either of those solutions, you shouldn't be writing a Doubly Linked List in other languages either (because they will have either pointers or reference counting/GC).
  - andrewflnr 4y ago
    "Those solutions" start off being hierarchical ownership or reference counting, but turn into "pointers or reference counting". Requiring pointers is implicit to the definition of linked lists, and calling it out here is silly. And you don't really need either ref counting (again, pretty obviously, witness every real world implementation) or hierarchical ownership outside Rust. Conceptually, the list as a vague concept owns all the nodes. The ownership just stops being expressible directly through references the way Rust wants it to be. But you don't have to re-invent hierarchical ownership to implement DLLs in other languages, because it's not really there in the problem. You just have to accept that they're always going to suck under Rust's ownership model.

ayhanfuat 4y ago

For completenes, here’s what Bjarne Stroustrup says on why you should avoid using linked lists: https://youtu.be/YQs6IC-vgmo https://youtu.be/YQs6IC-vgmo

db48x 4y ago
This is a video everyone should watch.

c-smile 4y ago

Why do we need to defend a hammer against a sickle? Each tool has its own value it was designed for ... Try to imagine LISP without lists ...

klysm 4y ago
A list can have different memory representations with identical semantics.
bsder 4y ago
> Try to imagine LISP without lists ... It's called Clojure. Getting rid of CONS (effectively removing singly linked lists) is a huge benefit.

tunesmith 4y ago

How do you detect a cycle with linked lists? :) I actually have a side project where I've run into this - it's a distributed directed graph structure where the nodes can send messages to each other. It's intended to be acyclic, but "walking the graph" is really only used to send truth values, which are combined with others to run Boolean logic. So in that case, the occasional cycle doesn't matter, because if the calculated boolean value matches that of the node's internal state, it just can cease propagating. So a structural loop won't turn into an infinite processing loop. The problem then becomes that I can't introduce NOT gates anywhere in a cycle, because then the bit will continue flipping and I'll get an infinite processing loop. So it seems my only hope is external processes that continually walk the graph and keep track of where it visited to try and detect loops, and I don't like how that scales...

bewaretheirs 4y ago
Set two pointers to the head of the list. Step through the list by one element per iteration with one of them, and with the other, step every other iteration. If the two pointers are ever again equal you've found a cycle. If you hit end of list, no cycle.
klysm 4y ago
Does the graph have static structure? I’m not sure if you’re describing something like an actor system.
- tunesmith 4y ago
  Akka cluster sharding :) Shape of the graph can change as processes are being run.
dragontamer 4y ago
With "just" a linked list, you need a turtle (advance one-node at a time), and a hare (advance two-nodes at a time). If the turtle and hare ever meet, you have a cycle. Otherwise, if the hare reaches the end of the list, you don't have a cycle.

waynecochran 4y ago

Another cool property about linked lists is that you can add an element to the head of a list without mutating the previous list. There are not many data structure that you can add an element to and leave the previous version unchanged. This form of immutability is a very nice feature that Lisp / functional programmers enjoy. Because of this, you can concurrently add an element to the head of a list to create new lists without having a critical section in your code.

robocat 4y ago
> you can concurrently add an element to the head of a list to create new lists without having a critical section The race is on: now you have two lists when before you had one?
- rileyphone 4y ago
  Every element of the list, from its own point of view, is another list.

lanstin 4y ago

I just used linked lists to make an LRU hard limit on the number of items in an in memory store. Each usage, the pointers are updated to move the item to the head. Each time the list is at the limit, the tail is removed and freed. I may take advantage of the machinery to make it go onto free list. This was Go and the DLL thing is my first use of generics.

layer8 4y ago

I think I first learned about linked lists in the context of programming for AmigaOS, which has a standardized form of (intrusive) linked lists that is used throughout the system. I remember being fascinated by the header node which serves as both the head and the tail of a list due to a “clever” field layout: https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues

Narishma 4y ago
Linked lists made more sense back then when memory access wasn't as slow compared to CPU speed.

deleted 4y ago

[deleted]

scottlamb 4y ago

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

pornel 4y ago
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.
- scottlamb 4y ago
  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 https://wiki.postgresql.org/wiki/Fsync_Errors
- colonwqbang 4y ago
  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.

stephc_int13 4y ago

The good thing about linked list is how easy they are to understand and use, almost trivial. The bad thing is that their cost nis ot obvious and not consistent (difficult to predict). I tend prefer simple arrays. This talk by Mike Acton is a good introduction to understand why going for the linked list as go-to data structure can lead to performance issues. https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc

koinedad 4y ago

They are really cool. Deleting an element by assigning next to next.next still blows my mind.

Jtsummers 4y ago
If you think that's neat, check out Dancing Links used for backtracking algorithms: https://en.wikipedia.org/wiki/Dancing_Links https://en.wikipedia.org/wiki/Dancing_Links

bitwize 4y ago

Linked lists are one of those things, like textual protocols, that people reach for because they're easy and fun but, from an engineering standpoint, you should never, ever use unless you can provide a STRONG justification for doing so. The locality of reference characteristics of vectors mean that, except for extreme cases, they beat linked lists almost every time on modern cached CPUs.

Jtsummers 4y ago

Language wars, editor wars, and now data structure wars. What random technical thing will people go to virtual blows over next?

keepquestioning 4y ago
https://www.reddit.com/r/slatestarcodex/comments/9rvroo/most_of_what_you_read_on_the_internet_is_written/ https://www.reddit.com/r/slatestarcodex/comments/9rvroo/most...
- B1FF_PSUVM 4y ago
  I'd note that the number of people creating content now is probably two or six orders orders of magnitude larger than before the internet, when it was just print/radio/TV/etc. Most that Joe Random could expect to get in print would be a Letter to the Editor, or a random passerby interview. The in-crowd was even more "unusual".

AtNightWeCode 4y ago

People must stop give attention to old garbage solutions that should not be used. Never use a link list if you don’t specifically need a link list. You probably don’t know why you would need one so don’t go there.

tester756 4y ago
It could be way better advice if you tried
int_19h 4y ago
If you stop "giving attention" to old solutions, people will simply reinvent them. Linked lists in particular are very easy to reinvent because they're so simple, and because their advantages are all evident even in a high-level language, while disadvantages require a more low-level understanding of modern compute performance.

belter 4y ago

“Does anyone use LinkedList? I wrote it, and I never use it.” - https://news.ycombinator.com/item?id=33418705 https://news.ycombinator.com/item?id=33418705

int_19h 4y ago
"Don't get me wrong; I love linked lists. They're as useful in C as they are in Scheme. But LinkedList is another matter entirely."

thedracle 4y ago

There was a time when memory was conventionally expensive, memory allocation of large blocks was slow, and small blocks was much faster (malloc would find a small block faster than a large one on a highly fragmented heap). Before having gigantic caches that would engulf nearly any sized contiguous list, linked lists were sort of vogue, frugal, and thought of as being fairly performant.

AstralStorm 4y ago
That time is still there in embedded hardware. Even potent ARM chips (except the cellphone ones maybe) have some KB of cache at best, and similar amounts of SRAM. While code size is still at a premium since XIP (execute-in-place from in-built flash) is slower.

nialv7 4y ago

It's odd that the author states they wrote the article in response to arguments on Twitter, yet they didn't show us the arguments this was a response to.

dreamcompiler 4y ago

Lisp of course was originally invented for manipulating linked lists and it came about in an era where cache locality wasn't an issue because computers in 1959 were speed limited by their CPUs rather than their memories. Cdr coding [0] solves several problems with singly-linked (cons-style) lists including cache locality and the 2x storage overhead of these lists. But it's not typically used except in dedicated hardware e.g. Lisp machines. It could in principle be revived fairly easily on modern 64-bit Lisp systems on stock hardware -- especially if such systems provided immutable cons cells. But it's probably not worthwhile because modern Lisp programmers (in Common Lisp at least) don't use lists all that much. CL has very nice adjustable arrays and hash tables that are easier and faster than lists for most purposes. [0] https://en.m.wikipedia.org/wiki/CDR_coding https://en.m.wikipedia.org/wiki/CDR_coding

ww520 4y ago

Linked list is useful when you are hurting for memory and need precision memory allocation, like in the kernel. You trade memory compactness for more operation time in dealing with its certain aspects.

AstralStorm 4y ago
And code size, let's not forget about that one. Plus you do not have a super smart memory allocator to prevent the hundreds of vectors from spraying the heap.

gslepak 4y ago

Anyone else getting a serious cert expired warning when visiting this site? The one I'm getting is also for the wrong name - registered for redis.io and expired on `Fri, 07 Aug 2020 11:30:03 GMT`. Issued by Let's Encrypt. Fingerprint: `07:BF:EA:59:DB:83:33:77:50:27:A8:C5:2F:80:F6:CA:E6:EC:E2:7D:01:DB:72:7A:AF:EE:69:DD:EC:2D:DA:F3` Seems like a MITM attack is going on.

gslepak 4y ago
Oh, nevermind, link was submitted in HTTP, but I have mandatory HTTPS enabled and the server is misconfigured.

m3kw9 4y ago

If you work on iOS, it’s really hard to do a better job than what the SDK has implemented in the arrays function.

cbreynoldson 4y ago

> You get what data structures made of links truly are: the triviality of a single node that becomes a lot more powerful and complex once it references another one. I don't think beginners actually make this connection for a while. Linked Lists are introduced analogously to arrays, sets, etc. Beginners think about Linked Lists in terms of what they already know. As a beginner, I thought of Linked Lists purely as non-contiguous arrays, even though there are deeper concepts behind them. Unless the beginners already have the perspective of "same having the power as the whole", I don't think this connection gets made for a while. Linked Lists don't expose so much possibility on their own.

fortran77 4y ago

I think the Rust people are de-emphasizing the importance of linked lists due to the glaring hole in the Rust language that makes it difficult to implement linked lists, and horribly awkward to do doubly-linked lists in safe Rust (See https://rcoh.me/posts/rust-linked-list-basically-impossible/ https://rcoh.me/posts/rust-linked-list-basically-impossible/ ) To save face, the Rust astroturfers are now skipping around saying "Linked lists aren't important"

c-cube 4y ago
The author is a known C programmer (he wrote redis). You're imagining things.
- fortran77 4y ago
  Yes; sorry I wasn't clear. I meant the people on HN commenting on "In defense of linked lists"

lacrosse_tannin 4y ago

Linked lists don't care about you. They aren't even alive.

TheDudeMan 4y ago
Is that a "pro" or a "con"?

Legion 4y ago

> (oh, dear Twitter: whatever happens I’ll be there as long as possible – if you care about people that put a lot of energy in creating it, think twice before leaving the platform) You mean the people that all just got fired?

javajosh 4y ago

Linked lists are cool, but he missed one reason why: how easily they become n-arry trees. A tree expressed like this is quite elegant and useful in a variety of domains, my favorite being a "trie" that is an n-arry tree that computes the label of each node as the string you get from the previous label plus the string in this node. It's a wild and hairy data-structure, but very cool once tamed.

sytelus 4y ago

Linked lists don’t need defense. It is unfortunate that job of vast majority of developers is rather benign. They don’t work on problems that requires complex algorithms and data structures beyond arrays and dictionaries. But interviewers keep asking those questions and give bad rep to these subjects. However, if you are working on building any real infrastructures such as search, deep learning, cloud, crypto, game engines, OS, compilers etc then you need linked lists, graphs, trees and myriad of algorithms surrounding them all the time. There is clearly different tier of developers who work on such infrastructure and those you simply utilize infrastructures others have built.

grog454 4y ago

There is no contiguous memory, arbitrarily resizeable alternative to a linked list in high performance concurrency is there? https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html https://docs.oracle.com/javase/7/docs/api/java/util/concurre...

deleted 4y ago

[deleted]

zebb 4y ago

> In defense of linked lists In defense of what? A brigade of null pointer exceptions? > Linked lists are conceptual. A node pointing to itself is the most self centered thing I can imagine in computing: an ideal representation of the more vulgar infinite loop. A node pointing to NULL is a metaphor of loneliness. A linked list with tail and head connected, a powerful symbol of a closed cycle. Oh, this article is complete satire. Bravo, you had me

subarctic 4y ago

Interesting, I have to disable HTTPS Everywhere on this site, otherwise it redirects me to https://redis.io/news/138 https://redis.io/news/138 and I get a 404 page.

raible 4y ago

FWIW I usefully use a "fake" linked list by adding a .next field to the struct in a compiler-allocated array of structs. On initialization I set the list head to &item[0], and in a trivial loop set the .next field of each entry (except the last) to entry+1. Why bother? Because I can then easily add a few extra structs to the beginning of the (contiguously-allocated) linked-list without having to reallocate the whole thing. Sure, pointer chasing with separately allocated structs is "slow", but I haven't yet measured to see if it's any different when (almost all) items are contiguous. If you would... - what sort of cache behavior should one expect of this on a modern laptop CPU? - I haven't seen this approach before, have you?

Sirened 4y ago
It depends on what prefetchers your CPU has and the actual underlying access pattern your accesses cause. If chasing next leads to a constant stride run through the array, you'll get identical performance to that of an iterative walk since essentially every high performance CPU since like 2010 supports stride prediction based on raw addresses. If .next sends you bouncing all over the area, you'll get complicated behavior since whether or not the data can be prefetched depends on the performance/existence of a pointer prefetcher, which is less common/more error prone. We know Apple's M1 have it due to some researchers using it as a side channel [1] but you'll have to do some digging on whether or not your laptop has one. Would make a nice post here if you do make the benchmarks :) [1] https://www.prefetchers.info/augury.pdf https://www.prefetchers.info/augury.pdf
- raible 4y ago
  Thanks for that, it's what I had hoped for (but again, have not yet measured). It seems to me it's a super-handy way of "modifying" a compiler-allocated array of structs. I'm sticking with it!

pugworthy 4y ago

Linked lists are great. But they have the problem that, almost always, whatever technical interview you have, someone asks you to whiteboard how to reverse one. And I answer, "I'd google it"

summerlight 4y ago

https://twitter.com/cpuGoogle/status/1415061974820421635 https://twitter.com/cpuGoogle/status/1415061974820421635 A nice explanation on rationales of using linked lists in OS kernel, from a Fuchsia developer. In short, it is almost guaranteed not to fail on most typical operations given the invariant is not broken, which make it suitable for cases where there's no fallback option left like kernel codes.

sudarshnachakra 4y ago

I guess linked lists as they are are very useful for implementing queues (particularly those that feed thread pools) where-in the costs of growable array is not needed and the cache locality does not matter (continuing with a thread pool example - It's almost a guarantee that having next element in the cache of the CPU which is not going to execute the next Runnable is a waste). In Java particularly the both array as well as the linked implementation of blocking queues should perform equally well. FWIW most queue implementations are linked lists.

NavinF 4y ago
The best implementations typically have a queue per thread and work stealing. The first threads to finish their assigned work will grab items from other queues, but until then you get perfect cache locality. Java's queues and global threadpool queues in general are pretty old hat.

DeathArrow 4y ago

While there's a certain use for linked lists - in operating systems kernels for example and as a programmer you absolutely have to know how linked lists work, there are other linear data structures which are more suited for general programming. To give a C# example, arrays, lists and dictionaries (hash tables) implement iterators so you can always know what the next element in collection is. Elements can be accessed by key or index in O(1),elements can be added in O(1). The case in which you absolutely have to insert an element in a particular position is rare so linked lists are seldom used. The same case is for C++, there is a vector class in STL but no linked list class. Same for Java.

selimco 4y ago
> The same case is for C++, there is a vector class in STL but no linked list class. Same for Java. Java does have a linked list in the standard library: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedList.html https://docs.oracle.com/en/java/javase/17/docs/api/java.base...
cyber_kinetist 4y ago
> The same case is for C++, there is a vector class in STL but no linked list class. No, there is std::list. https://en.cppreference.com/w/cpp/container/list https://en.cppreference.com/w/cpp/container/list > Same for Java. Also no, LinkedList exists. https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html https://docs.oracle.com/javase/7/docs/api/java/util/LinkedLi...

cyber_kinetist 4y ago

I think the whole "dynamic arrays" vs "linked lists" debacle is just a waste of time, since the two actually complement each other. - You can certainly implement linked lists using dynamic arrays, so you call the minimal amount of `malloc()`s and also make your items stored contiguously! You need to use indices instead of pointers, since you will lose pointer stability unless you use virtual memory (though the upside is that typically a uint32_t is enough for most cases, which only takes up half as much memory as a pointer). - A lot of data structures under the hood uses linked lists, even the ones that seem to use dynamic arrays on the surface. Have experience in writing a simple arena allocator? For the allocator to find a free space in the arena in O(1), you need to maintain a free-list data structure under the hood. And guess what: you need to write a linked list. Even your operating systems' `malloc()` itself probably uses linked lists under the hood. - Linked lists just come up inside so many other data structures, that you can essentially call it as the 'backbone'. For example: in compute graphics there is something called a half-edge data structure [0], which stores the geometry data of a mesh that's both compact, easy to iterate, and easy to do manipulations with (for instance, you can do things like insert/delete an edge/face easily in O(1) time, and more complex mesh operations can be implemented as well). And guess what? The vertices and halfedges are essentially stored in a complex web of linked lists. [0] https://jerryyin.info/geometry-processing-algorithms/half-edge/ https://jerryyin.info/geometry-processing-algorithms/half-ed...

Razengan 4y ago

Seems to me that all these arguments are rooted in the way computer memory is fundamentally implemented: Could it not be possible to re-architecture it so that it's more agreeable to arrays and lists, since that's how most data is used? I often wonder about the separation of CPU and RAM, of ways it could be done better. How about making it like neurons, where each "memory cell" is also a teeny tiny computer itself? (How DO neurons do internal computation anyway?)

deafpolygon 4y ago

Honestly, a lot of programming data structure concepts were difficult to grasp /until/ I truly understood how linked list works. It's a very simple concept in hindsight, but as a newbie programmer - this was an alien concept. Linked list? Just give me my array or built in List! Then I understood how to build a linked list and how it can be extended in various ways. They can be used to solve interesting problems. Many high level languages provide pre-baked implementations of LL but most programmers don't understand how they work under the surface. When I understood LL, I was able to apply that understanding to trees.

tomcam 4y ago

> Linked lists are simple. It is one of those rare data structures, together with binary trees and hash tables and a few more, that you can implement just from memory without likely stepping into big errors. One of the best engineers in Microsoft’s devdiv told me that he often gave a linked list implementation in C as a whiteboard assignment for interviewees and that no one ever managed a bug-free version. (I failed mine even after creating a full general purpose implementation on my own just a couple years before.)

antirez 4y ago
One thing is: you have 30 minutes of time and can compile and test and end with a working implementation. Another thing is write the code on a whiteboard, that is a process nobody ever follows in practice: very easy to make mistakes this way. Anyway doubly linked lists are easy to get wrong without compiling / testing.

pharmakom 4y ago

Immutable linked lists are a cornerstone of functional programming. However, Clojure has shown that the underlying implementation if often better done using a tree of contiguous memory blocks.

ordiel 4y ago

For an "article" starting with a ramble about how the author's life is being tragically affected by "the fate of Twitter", the sentence > get ready to read a sentimental post about a data structure Makes a looot of sense

sprawld 4y ago

Donald Knuth's Dancing Links paper is a beautiful exploration of the power of linked lists. He uses a table with doubly linked lists (for rows and cols) to solve omino tiling. The linked lists allow for an elegant unpicking of rows (and re-attaching when backtracking) The paper's a really enjoyable read, Knuth's tone throughout is "look at this, this is fun" https://arxiv.org/abs/cs/0011047 https://arxiv.org/abs/cs/0011047

deleted 4y ago
[deleted]

GnarfGnarf 4y ago

I have built my business on linked lists (genealogy trees). Paid for my house :o)

OOPMan 4y ago

Oh lord, can anyone make a post without whining on about Twitter?

fnordpiglet 4y ago

Linked lists also work great in a sharded distributed data structure. You can make changes to the list structure by simply changing reference at nodes and don’t need to move anything.

visarga 4y ago

That was my high school programming fun - implement linked lists and other data structures in TurboPascal. Pascal is a language that does not come with dynamic lists, only fixed size arrays and memory allocations. I had to build linked lists just to have a decent list primitive. A few years later I discovered Perl that comes with dynamic size lists, dictionaries and strings. Whoa, that was a treat, so very nice to use and efficient. To this day I prefer constructs made of lists and dicts 10x more than defining classes.

TurkishPoptart 4y ago

Can someone post an example of a linked list? I don't really understand this article.