Hacker News Reader

Comment by hnov | Hacker News Reader

Isn't a doubly linked list basically incompatible with Rust's idea of memory ownership?

It's definitely not a data structure that makes the borrow checker happy. Luckily it's also not a data structure that's required or desirable in 99% of cases, but the standard library still offers an implementation for those 1% so people don't try to write their own (turns out getting a doubly linked list correct isn't quite as trivial as it may seem).

I’m actually a bit surprised it’s in the standard library if it’s so uncommonly needed. Isn’t Rust’s stdlib tiny with a philosophy of letting the community fill in most things?

There were arguments made for its non-inclusion[1].

[1]: https://rust-unofficial.github.io/too-many-lists/sixth.html

I enjoyed reading this. A fun style.

It's at odds with it, but so are many other data structures found in the standard library. The solution is usually to use unsafe { } inside the data structure to allow for those criss-crossing pointers (while exposing safe, checker-friendly interfaces to the outside world)

This is a great resource that outlines several different strategies for implementing linked lists in Rust: https://rust-unofficial.github.io/too-many-lists/

From what I remember Rust has some kind of RefCell with weak references. Those could be used to make DLLs, if anyone can find a reason to use those. That said, you could also use zippers...

Now imagine writing the drop implementation for a DLL that doesn't cause a stack overflow.

RefCell<T> and weak references are two different things, but rust has both, yes.

AIUI, GhostCell and related patterns can be used to implement doubly linked lists in safe Rust. These patterns are quite obscure and hard to use in practice, though.

Reply on news.ycombinator.com