[hnov]

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

[proto_lambda]

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).

[Waterluvian]

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?

[estebank]

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

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

[Waterluvian]

I enjoyed reading this. A fun style.

[brundolf]

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/

[tmtvl]

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...

[steveklabnik]

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

[slaymaker1907]

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

[zozbot234]

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.