6 ms·
Surely the problems behind a doubly linked list apply to similar data structures (trees and graphs, notably - of which there are many more varieties than could
by rwmj 8y ago
Surely the problems behind a doubly linked list apply to similar data structures (trees and graphs, notably - of which there are many more varieties than could be covered by a standard library). Writing a tree without resorting to unsafe seems like something which would be important.
- amelius 8y agoYes, for example a DOM tree where every node has a backlink to its parent.
- TheCoelacanth 8y agoConsidering that one of the largest and most prominent Rust projects (Servo) is a browser, that is obviously not an insurmountable problem.
- pjmlp 8y agoServo has a GC implementation for handling DOM nodes. https://github.com/servo/servo/blob/master/components/script/docs/JS-Servos-only-GC.md https://github.com/servo/servo/blob/master/components/script... https://manishearth.github.io/blog/2015/09/01/designing-a-gc-in-rust/ https://manishearth.github.io/blog/2015/09/01/designing-a-gc...
- bzbarsky 8y agoIn a DOM tree, any live node in the tree needs to keep the entire tree alive. Which means you either need some sort of garbage collection setup, or reference counting (with cycle collection), or some sort of indirection where you really hold references to a "tree + node" pair and then have to worry about what happens when a node moves from one tree to another. Or something else, other than just having a bunch of objects that all point to each other without any explicit ownership semantics...