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.
Anyway, thanks for the thought-provoking post.
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.
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.
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-...
> 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.