In defense of linked lists

Linked lists are great. But they have the problem that, almost always, whatever problem you&#x27;re trying to solve would be better done with a regular resizable vector.<p>This includes problems that they should be great for, like insert into the middle or the front.<p>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&#x27;s large enough that it&#x27;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.<p>There are exceptions when you really should use an actual linked list, but your default should be a vector and not a linked list.

&gt; I thought of writing this blog post full of all the things I love about linked lists.<p>The blog post is short, and I think the author covered about everything.<p>Yeah, linked lists are sometimes appropriate, especially intrusive linked lists (the author called them &quot;embedded&quot; linked lists). The hate they get is a backlash against CS programs that introduce people to them early and don&#x27;t emphasize enough the reasons you should usually pick something else. If we have to err on one side or the other, I&#x27;d rather it be telling people not to use them.<p>btw:<p>&gt; Redis can be wrong, but both Redis and the Linux kernel can’t.<p>Yes, they can, and I&#x27;d rather avoid argument from authority altogether.

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

The most interesting thing about linked lists to me is how trivially it can be made lock-free multithreaded with atomics.<p>An array&#x2F;stack can be made multithreaded but it is non-trivial to handle the edge-cases. In particular, the ABA problem is rather difficult. I&#x27;ve seen many solutions to it (ex: a synchronization variable that puts the stack into &quot;push-only&quot; mode and then &quot;pop-only&quot; mode. There&#x27;s no ABA-problem if all threads are pushing!)<p>However, pushing&#x2F;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 &#x2F; lock free patterns.

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.<p>However I have a fun use for linked lists where this is NOT true.<p>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?<p>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.<p>In other words, with a few extra fields for clarity, here is the basic structure for subset sum of positive integers:<p><pre><code> { 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), } </code></pre> I leave figuring out the dynamic programming code to generate this as a fun exercise. Likewise how to extract, say, the 500&#x27;th subset with this sum. Both are easy if you understand linked lists. If not...well...consider it education!

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

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 &#x2F; 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.

Lisp of course was originally invented for manipulating linked lists and it came about in an era where cache locality wasn&#x27;t an issue because computers in 1959 were speed limited by their CPUs rather than their memories.<p>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&#x27;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.<p>But it&#x27;s probably not worthwhile because modern Lisp programmers (in Common Lisp at least) don&#x27;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.<p>[0] <a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;CDR_coding" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;CDR_coding</a>

For completenes, here’s what Bjarne Stroustrup says on why you should avoid using linked lists: <a href="https:&#x2F;&#x2F;youtu.be&#x2F;YQs6IC-vgmo" rel="nofollow">https:&#x2F;&#x2F;youtu.be&#x2F;YQs6IC-vgmo</a>

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

FWIW I usefully use a &quot;fake&quot; 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 &amp;item[0], and in a trivial loop set the .next field of each entry (except the last) to entry+1.<p>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.<p>Sure, pointer chasing with separately allocated structs is &quot;slow&quot;, but I haven&#x27;t yet measured to see if it&#x27;s any different when (almost all) items are contiguous.<p>If you would... - what sort of cache behavior should one expect of this on a modern laptop CPU? - I haven&#x27;t seen this approach before, have you?

Linked lists are one of those things, like textual protocols, that people reach for because they&#x27;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.

How <i>do</i> you detect a cycle with linked lists? :) I actually have a side project where I&#x27;ve run into this - it&#x27;s a distributed directed graph structure where the nodes can send messages to each other. It&#x27;s intended to be acyclic, but &quot;walking the graph&quot; 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&#x27;t matter, because if the calculated boolean value matches that of the node&#x27;s internal state, it just can cease propagating. So a structural loop won&#x27;t turn into an infinite processing loop.<p>The problem then becomes that I can&#x27;t introduce NOT gates anywhere in a cycle, because then the bit will continue flipping and I&#x27;ll get an infinite processing loop.<p>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&#x27;t like how that scales...

Donald Knuth&#x27;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)<p>The paper&#x27;s a really enjoyable read, Knuth&#x27;s tone throughout is &quot;look at this, this is fun&quot;<p><a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;cs&#x2F;0011047" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;cs&#x2F;0011047</a>

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: <a href="https:&#x2F;&#x2F;wiki.amigaos.net&#x2F;wiki&#x2F;Exec_Lists_and_Queues" rel="nofollow">https:&#x2F;&#x2F;wiki.amigaos.net&#x2F;wiki&#x2F;Exec_Lists_and_Queues</a>

One of the only times linked lists are &quot;undoubtedly the right option&quot; is if you&#x27;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.

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

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.

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.

Honestly, a lot of programming data structure concepts were difficult to grasp &#x2F;until&#x2F; I truly understood how linked list works. It&#x27;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&#x27;t understand how they work under the surface. When I understood LL, I was able to apply that understanding to trees.

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

I suspect the problem is that many people think of stuff like Java&#x27;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&#x27;t that strong. Especially with how cumbersome the List interface makes it to take advantage of the links.<p>That said, conceptually, linked items are everywhere; such that you can easily find how to list things following the links. You probably just don&#x27;t bother keeping that in a &quot;List&quot; structure in your code.

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<p>(See <a href="https:&#x2F;&#x2F;rcoh.me&#x2F;posts&#x2F;rust-linked-list-basically-impossible&#x2F;" rel="nofollow">https:&#x2F;&#x2F;rcoh.me&#x2F;posts&#x2F;rust-linked-list-basically-impossible&#x2F;</a> )<p>To save face, the Rust astroturfers are now skipping around saying &quot;Linked lists aren&#x27;t important&quot;

I&#x27;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.<p>&quot;Nobody uses this data structure stuff in real programming at work! You can forget it after college!&quot;

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

The good thing about linked list is how easy they are to understand and use, almost trivial.<p>The bad thing is that their cost nis ot obvious and not consistent (difficult to predict).<p>I tend prefer simple arrays.<p>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.<p><a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=rX0ItVEVjHc" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=rX0ItVEVjHc</a>

I think the whole &quot;dynamic arrays&quot; vs &quot;linked lists&quot; debacle is just a waste of time, since the two actually complement each other.<p>- 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).<p>- 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&#x27; `malloc()` itself probably uses linked lists under the hood.<p>- Linked lists just come up inside so many other data structures, that you can essentially call it as the &#x27;backbone&#x27;. For example: in compute graphics there is something called a half-edge data structure [0], which stores the geometry data of a mesh that&#x27;s both compact, easy to iterate, and easy to do manipulations with (for instance, you can do things like insert&#x2F;delete an edge&#x2F;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.<p>[0] <a href="https:&#x2F;&#x2F;jerryyin.info&#x2F;geometry-processing-algorithms&#x2F;half-edge&#x2F;" rel="nofollow">https:&#x2F;&#x2F;jerryyin.info&#x2F;geometry-processing-algorithms&#x2F;half-ed...</a>

&gt; 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.<p>Tongue-in-cheek, but this really made me smile. :-)

&gt; 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.<p>I don&#x27;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.<p>As a beginner, I thought of Linked Lists purely as non-contiguous arrays, even though there are deeper concepts behind them.<p>Unless the beginners already have the perspective of &quot;same having the power as the whole&quot;, I don&#x27;t think this connection gets made for a while. Linked Lists don&#x27;t expose so much possibility on their own.

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.

&gt; (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)<p>You mean the people that all just got fired?

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&#x27;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).<p>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.

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

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.

&gt; 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.<p>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.)

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&#x27;s more agreeable to arrays and lists, since that&#x27;s how most data is used?<p>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 &quot;memory cell&quot; is also a teeny tiny computer itself? (How DO neurons do internal computation anyway?)

<a href="https:&#x2F;&#x2F;twitter.com&#x2F;cpuGoogle&#x2F;status&#x2F;1415061974820421635" rel="nofollow">https:&#x2F;&#x2F;twitter.com&#x2F;cpuGoogle&#x2F;status&#x2F;1415061974820421635</a><p>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&#x27;s no fallback option left like kernel codes.

&gt; <i>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.</i><p>Well, if one likes linked lists enough, they can replace binary search trees &#x2F; 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.

I much prefer deques to linked lists when I need O(1) push&#x2F;pop but still want to keep some semblance of cache locality. Although you can&#x27;t splice two deques together as easily as two linked lists.<p>Sadly, you can&#x27;t really control the block size in C++&#x27;s std::deque so you can&#x27;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.

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 &quot;trie&quot; 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&#x27;s a wild and hairy data-structure, but very cool once tamed.

&gt; In defense of linked lists<p>In defense of what? A brigade of null pointer exceptions?<p>&gt; 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.<p>Oh, this article is complete satire. Bravo, you had me

There is no contiguous memory, arbitrarily resizeable alternative to a linked list in high performance concurrency is there? <a href="https:&#x2F;&#x2F;docs.oracle.com&#x2F;javase&#x2F;7&#x2F;docs&#x2F;api&#x2F;java&#x2F;util&#x2F;concurrent&#x2F;ConcurrentLinkedQueue.html" rel="nofollow">https:&#x2F;&#x2F;docs.oracle.com&#x2F;javase&#x2F;7&#x2F;docs&#x2F;api&#x2F;java&#x2F;util&#x2F;concurre...</a>

Anyone else getting a serious cert expired warning when visiting this site?<p>The one I&#x27;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&#x27;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`<p>Seems like a MITM attack is going on.

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&#x27; immutability&#x2F;segmentation or simplicity to implement make them the better choice.

Can someone post an example of a linked list? I don&#x27;t really understand this article.

Interesting, I have to disable HTTPS Everywhere on this site, otherwise it redirects me to <a href="https:&#x2F;&#x2F;redis.io&#x2F;news&#x2F;138" rel="nofollow">https:&#x2F;&#x2F;redis.io&#x2F;news&#x2F;138</a> and I get a 404 page.

“Does anyone use LinkedList? I wrote it, and I never use it.” - <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=33418705" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=33418705</a>

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.

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.<p>And I answer, &quot;I&#x27;d google it&quot;

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

While there&#x27;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.<p>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.<p>The same case is for C++, there is a vector class in STL but no linked list class. Same for Java.

Linked lists don&#x27;t care about you. They aren&#x27;t even alive.

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

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

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

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

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

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

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

My favorite typo&#x2F;brainfart so far this week has to be &quot;cache obviousness&quot; :)

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

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

For an &quot;article&quot; starting with a ramble about how the author&#x27;s life is being tragically affected by &quot;the fate of Twitter&quot;, the sentence<p>&gt; get ready to read a sentimental post about a data structure<p>Makes a looot of sense