Question is how to do these in Rust. An example might be a browser DOM: each node has a parent pointer, a list of child pointers, left and right sibling pointers, maybe a CSS node pointer, etc. Inserting or deleting nodes has to repair the pointers to and from the neighboring nodes as needed.

I know this is doable since obviously Servo (Rust's initial driving application) has to do it. I hope the answer doesn't involve the word "unsafe". But I am quite unclear about how to create such a structure under Rust's rules of pointer ownership, and also how to reliably reclaim storage when nodes and trees/subtrees are deleted. Plus there will be thread safety rules that should be statically enforced if possible.

I've heard that doubly linked lists in Rust are handled by an unsafe library, yet this seems even worse. Thanks.

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 3 points 2 weeks ago (1 children)

One note about doubly linked lists - I believe the received wisdom these days is that in almost all situations they're a bad algorithm to solve your problem. (I watched a video about it sometime... And read something in the Rust docs... I'm not an expert!)

I see other comments mentioning a hash map... Hopefully you've got some good options.

[–] [email protected] 3 points 2 weeks ago

Linked lists in general are cache unfriendly, though it helps if you have a relocating GC that puts the nodes back in order. The hash map idea is a possibility. I'm not actually trying to implement something like this. It's more of a question about Rust's approach from a PL perspective.