←back to thread

Flattening Rust’s learning curve

(corrode.dev)
451 points birdculture | 6 comments | 13 May 25 22:25 UTC | HN request time: 0.873s | source | bottom
Show context
dmitrygr ◴[13 May 25 23:24 UTC] No.43978986[source]▶
> Treat the borrow checker as a co-author, not an adversary

Why would I pair-program with someone who doesn’t understand doubly-linked lists?

replies(6): >>43979041 #>>43979123 #>>43979152 #>>43980150 #>>43980304 #>>43982624 #
mre ◴[13 May 25 23:43 UTC] No.43979123[source]▶
For people who don't get the reference, this might be referring to the notoriously gnarly task of implementing a doubly-linked lists in Rust [1]

It is doable, just not as easy as in other languages because a production-grade linked-list is unsafe because Rust's ownership model fundamentally conflicts with the doubly-linked structure. Each node in a doubly-linked list needs to point to both its next and previous nodes, but Rust's ownership rules don't easily allow for multiple owners of the same data or circular references.

You can implement one in safe Rust using Rc<RefCell<Node>> (reference counting with interior mutability), but that adds runtime overhead and isn't as performant. Or you can use raw pointers with unsafe code, which is what most production implementations do, including the standard library's LinkedList.

https://rust-unofficial.github.io/too-many-lists/

replies(4): >>43979377 #>>43979467 #>>43980233 #>>43980462 #
1. worik ◴[14 May 25 02:50 UTC] No.43980233[source]▶
I am working on a code base, that among its many glories and poo balls every list is a doubly linked list.

Stop!

If you are using a doubly linked list you (probably) do not have to, or want to.

There is almost no case where you need to traverse a list in both directions (do you want a tree?)

A doubly linked list wastes memory with the back links that you do not need.

A singly linked list is trivial to reason about: There is this node and the rest. A doubly linked list more than doubles that cognitive load.

Think! Spend time carefully reasoning about the data structures you are using. You will not need that complicated, wasteful, doubly linked list

replies(2): >>43980277 #>>43981044 #
2. dmitrygr ◴[14 May 25 02:59 UTC] No.43980277[source]▶
> There is almost no case where you need to traverse a list in both directions

But you might need to remove a given element that you have a pointer to in O(1), which a singly linked list will not do

replies(2): >>43980367 #>>43980371 #
3. dwattttt ◴[14 May 25 03:13 UTC] No.43980367[source]▶
If that's a specific use case you need to handle, it's O(1) again if you have a pointer to both the node to be removed and the previous node.

Whether it's more efficient to carry a second pointer around when manipulating the list, or store a second pointer in every list node (aka double linked list) is up to your problem space.

Or whether an O(n) removal is acceptable.

4. MeetingsBrowser ◴[14 May 25 03:13 UTC] No.43980371[source]▶
Getting the pointer to that element means randomly hopping around the heap to traverse the list though.

Linked lists are perfect for inserting/deleting nodes, as long as you never need to traverse the list or access any specific node.

replies(1): >>43992141 #
5. ◴[14 May 25 05:11 UTC] No.43981044[source]▶
6. dmitrygr ◴[15 May 25 05:32 UTC] No.43992141{3}[source]▶
You’re assuming no other data structure points to the element. It may. Example: implement a cache.

Each element is: key, value, linked list node for hash table bucket, linked list node for LRU. Hash table to look up element. Element is both a member of hash table and of linked list. Linked list is used as LRU for feeling memory when needed.

LRU never traversed but often needs removal and reinsertion.