In defense of linked lists
antirez.com
antirez.com
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.
Decomposing that vector into recursive subvectors solved the problem. Going from a few tens of millions of elements in a single contiguous vector (with consequent -- and bad -- heap fragmentation!) to nested vectors with a few thousand elements each brought us back online again.
Which is to say: Vectors are nice. Lists are nice. Use appropriate data structures for your scale, watch your semantic dependencies, and don't get hung up on dogma.
This does suggest functionality that the OS should provide: let the program remap memory somewhere else in its address space to obtain a larger contiguous chunk of addresses without copying data. This wouldn't help much if you have direct pointers, but I think e.g. Java has a layer of indirection that would let it benefit from remapping to grow ArrayLists. I don't know if things already work this way. It should make speculative fetches easier for the processor since now it understands what you're doing via the memory map.
Edit: taking this idea a little further is actually fascinating: use the type system to separate objects into pools based on type, and instead of pointers, use indexes into your pool. You can move the pool for free to grow/shrink it. I think you could even do this with pointers and full hardware acceleration today if you used the high bits to tag pointers with their types and used remapping at the hypervisor level to move the pools (so the address in the application level doesn't change). You could do some crazy stuff if the application could coordinate multiple levels of virtual memory.
But you should not play virtual memory games at runtime in an application that you expect to be scalable. Unmapping memory or changing its permissions requires propagating the change to all threads in the process. On x86, the performance impact is dramatic. On ARM64, it’s not as bad but it’s still there.
Also, even 64 bits can go fast when you start using high bits, separate pools for different purposes, etc.
I don't know if anyone has done research on integrating data structures and OS functionality in this way. Interesting idea.
We needed to get things running again rather quickly, though :-)
Edit: Let's call it "memoveouttamyway"
Unfortunately, libstdc++ does not (to my knowledge) use realloc(3) or mremap(2) for vector resize, nor could it in many situations due to the semantics of C++.
[1] https://github.com/bminor/glibc/blob/15a94e6668a6d7c5697e805...
I don't know where the line is, but in general you are probably not close to that line so default go vector. However as your point is, sometimes you are over that line.
I would hate to have to do a full balanced b-tree on short notice. (We also had rather terrible extra requirements that made using an off-the-shelf thing from, say, the STL work in our environment).
One exception is ML style languages where singly linked lists get a big syntax advantage (Haskell only half counts because most of its lists are really just iterators). I think this was, in hindsight, a mistake for a widely used language. It’s also a source of pointless pain for learners (eg I don’t think there’s much benefit to people having to write lots of silly tail-recursive functions or learning that you have to build your list backwards and then reverse it). Another exception would be some lisps where lists are everywhere and the cons-cell nature of them makes it hard to change.
often they're sufficiently maximal.
That makes sense, given how abstract things have gotten. Decades ago there was an article that showed the penalty for non-linear data access was massive. That was before speculative access, branch prediction and cache prefetching were standard features. The performance hit today would be even more (except presumably for machines that have implemented the speculative execution security mitigations).
You're right to point out that given the performance characteristics of most modern CPUs, accessing memory linerally is optimum. But it doesn't necessarily follow that all collection data structures should be stored as a vector. Consider a collection traversed very slowly relative to the overall computation. There may not be any cache win if the line's always evicted by the time you come back to it.
Your misconception lies in the assumption that the only conceivable use case is iterating over a preallocated data structure to do read-only operations.
Once you add real world usages, with CRUD operations involving memory allocations/reallocations then your misconception about cache crumbles, and you start to understand why "people are arguing over this".
In fact, on modern architectures it may be faster to iterate over arrays just to take advantage of l2/l3 behaviors.
I think tools that result in greater transparency at lower levels will probably emerge, something like a compiler-generated dynamic analysis + pre-flight checklist hybrid. But since it’s so low-level, it might actually affect results, which may be a problem. I think intel vtune seems interesting in that regard.
As soon as you start adding or deleting items in the middle, the game changes because the data you need to move is not contained in the cache anymore (except for small arrays).
I can even imagine a workflow that uses both data structures: an app could build up a linked list with the data it reads from an external file, for example, where they can be scattered and not in order; when the file is finally closed, the data are considered read-only and rearranged into an array for the remaining part of the execution.
So don't dismiss linked lists as inefficient "a priori", which is exactly what antirez claims in the article.
Say you want to add an element in the middle of an N-element ll/array.
For the linked list, this means you need to do 2 * N/2 memory reads (read value, read next pointer), which will mean on average N/2 cache misses, to reach the element at index N/2. Then you'll do O(1) operations to add your new element. So, overall you've done O(N) operations and incurred O(N) cache misses.
For an array, there are two cases:
1. In the happy case, you'll be able to re-alloc the array in-place, and then you'll have to move N/2 elements one to the left to make room for your new element. You'll incur one cache miss to read the start of the array, and one cache miss to read the middle of the array, and one cache miss for realloc() to check if there is enough space. The move itself will not incur any more cache misses, since your memory access pattern is very predictable. So, overall you've done O(N) operations, but incurred only O(1) cache misses - a clear win over the linked list case.
2. Unfortunately, sometimes there is no more room to expand the array in place, and you actually have to move the entire array to a new place. Here you'll have to move N elements instead of N/2, but you'll still incur only 1 cache miss for the same reason as above. Given the massive difference between a cache miss and a memory access, doing N operations with 1 cache miss should easily be faster than doing N/2 operations with N/2 cache misses.
The only access patterns where the linked list should be expected to have an advantage are cases where you are adding elements very close to an element which you already have "in hand" (e.g. at the head, or at the tail if you also keep a pointer to the tale, or to the current element if you're traversing the list while modifying it). In those cases, the linked list would need O(1) operations and cache misses, while the array would need O(N) operations and O(1) cache misses, so it would start to lose out.
The only problem is that use cases evolve, and what was fine suddenly isn't, anymore.
Of course, the same unintuitive tradeoffs tend to apply even if there isn't much caching to worry about. A trivial linear iteration is often faster than a more elaborate algorithm when the input is small.
At gross complexity / fragmentation / to your memory allocator.
Linked Lists are definitely easier to use if you're ever in a position where you're writing your own malloc(). The infrastructure needed to cleanly resize arrays (and also: the pointers all going bad as you do so) has a lot of faults IMO.
EDIT: In particular, linked lists have a fixed size, so their malloc() hand-written implementation is extremely simple.
It does take some discipline to avoid the storage of pointers, but once you get used to that it’s quite fine.
Source: I work on VPP, which uses vectors quite extensively.
And the solution to "pointers to elements of a vector going bad" is don't save pointers to elements of a vector.
From the article https://github.com/dtrebilco/Taren/blob/master/Articles/Eras...
How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from?
>> your default be a vector and not a linked list
The default should be to understand the problem.
If you want lock-free atomic data structures there are lots of variations (like AVL trees) that can be used as the underlying storage and just like mentioned above it tends to work well for most use cases and access patterns.
If N is fairly small and/or you allocate most of your linked list around the same time it may not matter which is why measuring your actual program with real-world data and access patterns is so important. eg if in production logging or other malloc traffic ends up making your linked list nodes spread out in memory perf is not going to match what you tested at your desk.
Often an algorithm can operate on an entire cache line's worth of data before main memory can chase down a single pointer. Modern CPUs hide that with prediction but even if the address prediction is 100% accurate if the result is a pointer loading chain you run out of pre-fetch slots pretty fast.
To give concrete numbers if DRAM is not busy refreshing and there is no bus contention or inter-core contention then we might get 60-100ns access times all told. If we have a 3Ghz CPU then that's 300 cycles waiting around doing nothing... for each pointer that needs to be dereferenced. For a vector after the first 300 cycle hit the rest would be free - following nodes are in the cache line and address prediction will pre-fetch subsequent cache lines as well, allowing pre-fetching to stream data ahead of when it is needed.
Both an array and a linked list are O(n) for adding in the middle. In an array, you finding the middle element is O(1), then moving the rest of the array is O(n) [you have to move n/2 elements]. In a linked list, finding the middle element is O(n) [you have to traverse n/2 elements], but adding it is O(1).
So, asymptotically there is no difference. In practice though, the linked list traversal will cause O(n) cache misses to reach the middle element (since we are traversing random memory), while the array move will only incur O(1) cache misses (since we are accessing memory in order) - so, the array will actually win in practice.
Edit: Note that I also don't know where the GP got the O(lg n).
I think your parent's point is that if you're a C++ programmer, recognizing that vectors outperform other data structures for most use cases is what separates a good engineer from a great one. Often even for things that require lookup (i.e. vector outperforming a set).
During code reviews, a senior C++ programmer in my company (formerly sat in the C++ standards committee) would always demand benchmarks from the developer if they used anything else. In most cases, using representative real world data, they discovered that vectors outperformed even when the theoretical complexity of the other data structure was better.
A great engineer knows the limitation of theory.
Of course, my comment is only regarding C++. No guarantees that vectors are great in other languages.
Valid uses for a linked list are extremely niche. Yes, you can name some, and I can name several valid uses for bloom filters. Just because a simple linked list is easy to implement does not mean it should be used, any more than bubble sort should be used for its simplicity.
// LinkedListItem[k]: item[k], prev[k], next[k]
std::vector<T> item;
std::vector<uint> prev;
std::vector<uint> next;
Imagine the Euler Operators on a manifold (ie a 3D mesh) or on a planar graph, but on a vector instead of on a DCEL.
For those you have to store object pointers in the vector, instead of copies of the objects. That works and is often done, but it defeats or reduces the cache locality perfornance improvement which motivates using a vector in the first place.
On an in-order CPU an intrusive list (pointers inside the objects) can be traversed faster than a vector or B-tree of object pointers, though a non-intrusive list (list of nodes containing object pointers) won't be faster. On an out-order CPU with heavy speculative execution it is less clear cut because the vector allows successive objects to be dereferenced speculatively in parallel to a limited extent, while this is not possible traversing an intrusive list.
If the list is going to be traversed looking for objects based on some filter criterion such as flags or a number comparison, based on non-mutable state (or where it's ok for mutation to be expensive), traversal can be sped up by storing criterion data in the vector alongside the pointers, or in a second vector, to avoid dereferencing every touched object pointer during traversal.
Resizing a vector brings the whole of it into cache, potentially dragging all of it all the way from actual RAM. Prepending an entry brings nothing into cache.
Cache is king.
I don’t do low level code on modern systems; is there not a way to just blit chunks of memory around without a CPU looping it’s way through word by word carrying out MOVQ instructions which do a full RAM read/write?
If you’re streaming data out of memory to a PCIe bus or something, that wouldn’t go via cpu cache, right? There’s some kind of DMA model, so there’s something in the system architecture that allows memory access to be done off-CPU (I vaguely think of this as being what the northbridge was for in the old school x86 architecture but I’m fuzzy on the details?).
Mechanical copying of byte arrays feels like something a CPU should be able to outsource (precisely because you don’t want to pollute your cache with that data)
There is a reason why it's hard to create either a bare linked list or a bare array on modern language. It's because both are bad extremes, and the optimum algorithm is almost always some combination of them.
Do you have some benchmarks demonstrating your claim?
Adding an element in the middle of an array vs the middle of a linked list actually has the same asymptotic complexity (O(n)), but far better cache impact for the array (since moving a contiguous block of n/2 elements should only incur 1 cache miss, while reading n/2 randomly distributed nodes of the list will incur on average something like n/4 cache misses). Adding closer to the beginning of the linked list is faster, but adding close to the end of the vector is faster still, so overall with random access, the vector should win.
One a Lisp Machine from the 80s/90s the system saves a type sorted and locality optimized memory image, from which it later boots the Lisp system. Additionally to the typical GC optimizations (incl. integration with the paging system) it also provided CDR coding, which allocates lists as continuous memory. The GC also creates those CRD coded lists. CDR coding fell out of fashion in modern Lisp implementations, because the space and time savings aren't that great to justify the more complex implementation.
A standard ring buffer does copies/fill. A ring buffer of pointers has similar performance characteristics to a linked list.
Kinda weird how rare it seems to be.
And indeed, I don't recall seeing something like that. At a first glance O(log n) seems easy to do in the average case, but perhaps not in the worst case.
One important exemption is when you want your datastructure to be persistent.
See https://en.wikipedia.org/wiki/Persistent_data_structure
But for many applications there are also better persistant data structures than linked lists around.
Two: Lisp doesn't actually care whether there are literally linked lists behind everything. Today you would use a different data structure reflecting the hardware you have.
By the time Xerox, MIT, TI started delving into Lisp machines, the language had already gotten support for stack allocation, value types, arrays, structures (records).
Same applies to its big brother Scheme.
(a1 (b1 (c1 c2 c3) b2 (c4 c5)) a2 a3) is a tree.
Linked lists are optimal for head access; not random access. For random access, yes a vector would be better.
As any generalization this one too is, of course, incorrect.
Outside of the realm of academia, the need to keep data pieces in several containers at the same time, with no heap operations on insertion or removal and O(1) removal is very common, especially in the kernel space and embedded contexts. The only option that fits the bill - you guessed it - are the linked lists.
In the real world of application development when choosing between Vector and LinkedList the answer is almost always Vector. There are, of course, certain problems where LinkedList is always the correct answer.
However for all problem that have chosen either Vector or LinkedList as their container of choice a super majority should choose Vector.
But the javascript array type is much more complicated. It intelligently changes its internal structure based on how you use it - which is pretty wild.
And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.
For example, I'm wondering how the CPU knows what the next item in the list to prefetch it. Unlike the next item in an array, list items could be pointing anywhere in process memory.
Also, what counts as a modern CPU in this context? Are we talking latest generation desktop CPUs from Intel, or anything after Core 2 Duo? How about mobile devices with ARM CPUs? Would those just be ignored?
Is there a benchmark?
It is extremely difficult, maybe impossible, to design a prefetcher that can predict the next cacheline(s) to prefetch while traversing in a linked-list. I am not aware of a single CPU that can do this consistently. For instance, if you run multichase (a linked-list chaser) on GCP servers, you generally get the expected memory latency (~70-100ns, depending on the platform).
There are some niche use cases where linked lists are good. Lock-free queues are one, and another big set of use cases is where you need hard O(1) insert even with a high constant factor, not amortized O(1).
Vectors are basically perfect for queues.
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.
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.
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.
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.
Vecdeque can cheaply pop/push front and end too. Arrays have swap-remove. You may not need to grow if you preallocated a capacity. Freelists can be a stack, or you can choose a data structure that doesn't allocate objects individually so you don't need the freelist in the first place.
Another thing that is C-specific is that most objects are treated as unmovable and their address is their permanent identity. Without language features for prevention of dangling pointers, moves are asking for trouble. This favors linked lists and pointery data structures over contiguous containers and inlined data.
> Yes, they can, and I'd rather avoid argument from authority altogether.
Pretty sure that was a joke, considering the overall light-heartedness of the whole post.
You almost always want to unroll your linked linked lists, so that items are fetched in blocks. But this rarely happens in C because it’s premature optimization in C. In C++ or Rust you can write the code once in a generic data structure and enjoy the benefits to the end of time.
That all said, I think we should still teach them in CS because understanding linked lists is the first step to understanding trees.
Proof by authority is the worst. Yet, linux kernel can have valid reasons for, but they are intrusive lists with the data having a pointer to the next.
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.
If you combine intrusive linking with a pool allocator, you can have decent locality too.
Scrubbing through things quickly is empirically more common, hence the standard advice to use vectors by default.
But yeah, I understand they took the task struct out of the kernel stack now.
Edit: difficult being an understatement, you'd need to solve the halting problem to be able to rewrite any self-referential pointers to stack objects wherever they may be.
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.
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/69413598d2660054...
I did it only for compatibility and would still prefer vectors whenever I can use them. Nevertheless, I put some efforts into coming up with a useful and high-performing implementation. To give an example: My `append` function is O(1) and not a poor O(N) version that you rightfully criticized in your tweet.
[1] https://colinfinck.de/posts/nt-list-windows-linked-lists-in-... [2] https://www.youtube.com/watch?v=IxhZIyXOIw8
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.
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.
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.
https://github.com/google/re2j/blob/dc7d6e5d41225dc0825ea6fe...
Java doesn't suffer from pointer address ABA but I did have to handle reinsertion (except when the stack had only one element).
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),
}
> 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)#:~:t...
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?
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 ;)
This LinkedList obsession is a bit bizarre to me, and tends to come from older programmers who come from a time when coding interviews involved writing linked lists and balancing b-trees. To me though it also represents the stubbornness of C programmers who refuse to consider things like growable vectors a solved problem. My reaction to the LinkedList coders is not "well Rust needs to maintain ownership", its why does your benchmark for how easy a language is involve how easy it is to fuck around with raw pointers?.
LinkedLists are a tool, but to C programmers that are an invaluable fundamental building block that shows up early in any C programmers education due to how simple they are to implement and the wide range of use cases they can be used for. But they are technically an unsafe data structure and if you willing to let some of that stubbornness go and finally accept some guard rails, you have to be able to see that a data structure like linkedlists will be harder to implement.
It has nothing to do with the language; implementing with LinkedLists with any sort of guardrails adds a ton of complexity, either up front (e.g. borrowchecker) or behind the scenes (e.g. a garbage collector). When you accept this fact, it becomes ludicrous to imply that a LinkedList implementation is a good benchmark for the ergonomics of a language like Rust.
You're acting like it's some epic burn on Rust that there's some ugly code in its stdlib. It's not. Stdlibs are like that. Furthermore, as others have pointed out, linked lists in particular are a pathological case for Rust, meaning you're pointing and snickering at a special case of a special case. Most people never have to write or look at that kind of code.
This isn't the best solution for all cases! Sometimes performance is more important than safety, and there are things you can't do as efficiently without mutable data. And sometimes (especially for systems that are reactive rather than transformational, in Harel and Pnueli's terms, or for libraries) a garbage collector is an unacceptable cost.
And Rust is actually reasonably good at singly-linked lists; it's just doubly-linked lists (which inherently feature mutation) that are troublesome. Singly-linked lists with sharing through Arc are a little more expensive in Rust than in something like GHC, Ikarus Scheme, or OCaml, but that's hardly a damning criticism of Rust.
But you seem to be claiming that linked lists are unsafe in any language, and to anyone familiar with functional programming, that claim is obvious nonsense. Did you intend it?
As for the Option type, it is exactly what it says. It's an optional, non-nullable node generic over type T. I suppose generics, optionals and the idea of non-nullable types might be exotic at first, but this is not a problem with Rust as much as it's a problem with C not being able to express these concepts in the first place and instead expecting you to spray null checks all over the place!
Learn Rust with entirely too many linked lists (2019) - https://news.ycombinator.com/item?id=22390662 - https://rust-unofficial.github.io/too-many-lists/index.html
In this series I will teach you basic and advanced Rust programming entirely by having you implement 6 linked lists. In doing so, you should learn:
- The following pointer types: &, &mut, Box, Rc, Arc, const, mut, NonNull(?)
- Ownership, borrowing, inherited mutability, interior mutability, Copy
- All The Keywords: struct, enum, fn, pub, impl, use, ...
- Pattern matching, generics, destructors
- Testing, installing new toolchains, using miri
- Unsafe Rust: raw pointers, aliasing, stacked borrows, UnsafeCell, variance
https://github.com/llvm-mirror/libcxx/blob/master/include/li...
And this is with several years cpp experience, and maybe a few months of Rust on and off.
Having said that - yes, it's not pretty. About the same length though.
As for the unsafety, I would assume the authors of collections know what they are doing and do that for performance.
is the "In" in "LinkedIn" deliberate here or just a typo that was made twice?
This is a great resource that outlines several different strategies for implementing linked lists in Rust: https://rust-unofficial.github.io/too-many-lists/
The race is on: now you have two lists when before you had one?
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.
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.
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?
It seems to me it's a super-handy way of "modifying" a compiler-allocated array of structs. I'm sticking with it!
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...
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.
Another notable advantage of Brent's algorithm is that it automatically finds the cycle length, rather than (in Floyd's case) any multiple of the cycle length.
https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algori...
To be clear, http://trout.me.uk/gc/recycler-overview.pdf
There's also a paper with the full algorithm in that directory.
It's how Nim's ORC collector works.
(note that yes, I know, this is for collection, not cycle detection in general, but it's also brilliant and works)
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.
Or to save the comparisons make the thing the first node points to have a stop flag of some sort.
Head -> Node1 -> Node2 -> Node3
^ |
+-----------------+
The paper's a really enjoyable read, Knuth's tone throughout is "look at this, this is fun"
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.
Like any tool, it has its place. As long as you're not traversing large linked lists, they're probably fine.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nodepointer = None
Where linked lists really seem to come into play is with custom manual memory allocators in embedded programming, something of a niche subject.
Not unless you manually disable gc.
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"
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.
In practice, it seems unusual for it to have any advantages over just using an ArrayList in typical JVM applications.
This ignores constant factors and cache coherency, of course. More, it also ignores that most lists that folks will make have a VERY predictable access pattern. Typically just a one way scan, if any traversal at all. With very few inserts, and mostly just appending.
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.
(See 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"
"Nobody uses this data structure stuff in real programming at work! You can forget it after college!"
https://github.com/tigerbeetledb/tigerbeetle/blob/main/src/f...
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 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.
- 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-ed...
Tongue-in-cheek, but this really made me smile. :-)
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.
You mean the people that all just got fired?
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.
Java's queues and global threadpool queues in general are pretty old hat.
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.
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.)
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?)
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.
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.
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.
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
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.
And I answer, "I'd google it"
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.
No, there is std::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/LinkedLi...
Java does have a linked list in the standard library: https://docs.oracle.com/en/java/javase/17/docs/api/java.base...
However, Clojure has shown that the underlying implementation if often better done using a tree of contiguous memory blocks.
Each tool has its own value it was designed for ...
Try to imagine LISP without lists ...
It's called Clojure.
Getting rid of CONS (effectively removing singly linked lists) is a huge benefit.
> get ready to read a sentimental post about a data structure
Makes a looot of sense