3 ms·

a parent field. a doubly linked list

• littlestymaar 3y ago
  Doubly-linked list is something you have almost no reason to ever write. Parent field is something where you have a clear hierarchy (it's not really “cyclic”, so it's the perfect use-case for weak references). When coming from a managed-memory language, this obviously requires some conceptual effort to understand why this is a problem at all and how to deal with it, but when compared to C or C++, the situation is much better in Rust.
  • jacobgorm 3y ago
    Also, a parent field is something you should be able to infer, e.g, keep a stack of parents as you traverse down a search tree following the child pointers, instead of storing parent pointers in the tree nodes.
    • akoboldfrying 3y ago
      That's assuming you traverse the tree down from the root each time. Often you do, but there are cases where you don't -- e.g., if your goal is to determine the lowest common ancestor of two given nodes.
• tialaramex 3y ago
  Your parent said "frequently encountered" and while it's probably true that doubly linked lists may be "frequently encountered" in some people's code they're usually a bad idea and "don't use a list here" is often the right fix, not "conjure a way to make that safe in Rust". It's very noticeable how often people who "need" a linked list actually only wanted a queue (thus Rust's VecDeque) or even a growable array (ie Vec). Aria has a long list of excuses people offer for their linked lists, as well as her discussion of the time before Rust 1.0 when she sent lots of Rust's standard library collections to that farm up-state but wasn't able to send LinkedList. https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/