Comment by ekidd | Hacker News Reader

Comment by ekidd | Hacker News Reader

Yeah, a doubly-linked list is basically the worst possible choice for your first program in Rust. This is because Rust likes all of your memory to have one clear owner. And this means that cyclic data structures are unusually difficult compared to almost any other first program you might choose.

But if you really want to know how to do it, there's a really good tutorial on the subject titled "Learning Rust With Entirely Too Many Linked Lists": http://cglab.ca/~abeinges/blah/too-many-lists/book/

This will walk you through multiple different kinds of linked lists, and show you how to implement each in Rust. Along the way, you'll learn more about Rust's ownership system than most working Rust programmers generally need to know.

Personally, I've written quite a bit of production Rust code, and I've done so without ever touching 'unsafe' or needing a linked list. If I really did need a linked list, I'd either grab a good one off crates.io, or just knock out a quick one using `unsafe` and raw pointers. I mean, Rust can do basically anything C does if I ask nicely. It's just that if I choose to write "C in Rust", then I get about same safety guarantees that C offers.

OP here. In hindsight, this is 100% correct. Hopefully this post will help people avoid my mistakes.

Just out of curiosity, didn't you do a google-search for "linked list in Rust" when you ran into problems? Or isn't that your style? :)

Anyway, thanks for the thought-provoking post.

I did. I found the book of linked lists at the bottom of the post. After reading and appreciating the complexity I didn't want to deal with, I just wrote it in Go

No jugement here, but I curious to understand your situation: if you didn't want to deal with the complexity of the implementation, why didn't you just import a linked list from the standard library ? Did you just want to implement a linked list for learning, but still put the minimum effort in the process ?

The standard library linked list doesn't support inserting in the middle

Yeah also even if you think you need a linked list, you probably don't. Vectors are faster in nearly every case, even ones that linked lists are designed to solve.

I’m mightily curious to know how you decide which double linked list to get from crates, isn’t there a clear best implementation? Are the differences/trade offs described somewhere? And if you can get one from crates, why would you implement your own with unsafe at all? Wouldn’t using an existing C linked list be more convenient?

So the first question: Why are you using a doubly-linked list? :-)

Due to the way modern processors work, following long chains of pointers is massively expensive (unless can you carefully control where all of the memory was allocated). There's a whole section discussing this in the "Too Many Lists" book. Basically, following pointers to unpredictable places will eventually defeat your processor's caches. You could easily wind up running a thousand times slower than if you used the cache well.

So you first want to look at data structures which store many elements in a single block, so that they're adjacent in memory and you won't have to chase nearly as many pointers.

- If you just want an ordered group of elements, use a "Vec", which is similar to a C array.

- If you're going to add elements at the back, and remove them from the front, look for a queue. These can be implemented with ring buffers or slabs of memory containing multiple elements at a time. There's a couple in the standard library.

- If you need to keep elements in order and search for them, you might actually want a B-tree, which again uses slabs of memory. There's a nice BTreeMap in the standard library.

Basically, by the time you've analyzed your problem, there's a 95% chance that a doubly-linked list was just the wrong data structure. Cache locality just has too big an effect on performance.

But if you really need a linked list, go to https://crates.io/ and search for "linked list" or "doubly linked list." Flip through the first page or two, and look for something with lots of downloads and nice docs. Check if it supports the APIs you want for your use case.

Also take a look at petgraph, which is an awesome Rust graph library: https://crates.io/crates/petgraph This has a zillion downloads (by Rust data structure standards), plenty of reference docs, and good support. It knows about cache locality. And a linked list is really just a special case of a graph.

But basically, you shouldn't be using doubly-linked lists unless you know exactly why you need one. They're a nice teaching exercise (except in Rust or functional languages) but they're actually pretty specialized.

>So the first question: Why are you using a doubly-linked list? :-)

Honestly there is only one legitimate usecase for a linked list that can only be solved suboptimally with a continguous array. Removing elements in the middle of a list assuming you already know the pointer to the linked list node.

In a linked list you can just overwrite the previous node to link to the next node.

However what I do is I just swap the element with the last one in a vector and delete the last element. This doesn't preserve the order of the list but for me this has never been a significant issue.

”there is only one legitimate usecase for a linked list that can only be solved suboptimally with a continguous array. Removing elements in the middle of a list assuming you already know the pointer to the linked list node.”

You will be surprised to see how large a memmove you can do on modern hardware in the time it would chase those pointers.

For an extreme example (moving array data gets slower if your elements grow larger), see https://youthdev.net/en/performance-of-array-vs-linked-list-...

The usecase imtringued was talking about:

> assuming you already know the pointer to the linked list node

For example a LinkedHashMap where a hash provides the primary means of looking up elements and the nodes contain an intrusive linked list. Removing an element from that list doesn't involve chasing pointers from the start of it.

The linked benchmark is for a different scenario.

Not sure why you'd need to use something from crates.io; there's a doubly-linked list in the standard library[1]. That being said, the standard library documentation itself strongly suggests that you use a VecDeque in most cases[2].

[1]: https://doc.rust-lang.org/std/collections/struct.LinkedList.... [2]: https://doc.rust-lang.org/std/collections/index.html#use-a-l...

Reply on news.ycombinator.com