5 ms·

> Complicated pointer-type data structures like linked lists If a singly linked list is a complicated data structure then what's a simple one?

• nickpsecurity 8y ago
  An article you might find helpful is this one on why imperative algorithms are harder to mathematically verify than functional ones: https://semantic-domain.blogspot.com/2018/04/are-functional-programs-easier-to.html https://semantic-domain.blogspot.com/2018/04/are-functional-... You don't need to be a mathematician to follow it with this excerpt summarizing its key point: "The difficulty of imperative programming arises from the combination of state, aliasing and procedure calls. Any two of these features can be handled without that much difficulty, but the combination of all three effectively makes reasoning (nearly) as difficult as correct concurrent programming. " The garbage-collected languages let you ignore the aliasing problems with a performance penalty. Rust in safe mode without GC forces you to (a) deal with it and (b) deal with it in a way that works for all inputs (type/memory safety). That usually requires mathematical verification using tools such as separation logic. Rust's method is much easier to use with tradeoff of limitations on expressing code in certain ways. Folks that get along with the borrow-checker say it helps to design the program around data and easy methods of using it versus starting with control flow forcing it on a data structure. I'll also add that linked lists are inherently hard to get right on all inputs regardless of low-level language. They're actually a popular way to test new, mathematical methods for specifying and proving algorithms correct. Fortunately, Rust folks have a goto write-up on linked lists in their language: https://cglab.ca/~abeinges/blah/too-many-lists/book/ https://cglab.ca/~abeinges/blah/too-many-lists/book/
• staticassertion 8y ago
  There aren't really simple data structures that involve pointers. Pointers are just hard (where hard means they require programmers to hold state in their head), and rust makes that explicit. The reality is that implementing data structures that require pointers is not a typical task, and they're ideally provided by the stdlib or crates.
• tetromino_ 8y ago
  A heap would be simple. Rust's ownership rules make it hard to implement data structures composed of nodes that own references to other nodes. (This includes linked lists, binary trees, and naive implementations of graphs.) There is a reason for this - it's rather tricky to implement such data structures truly safely in any language without introducing hidden assumptions, that's why they are so frequently seen in interview questions for java and c++ coders.
  • SilasX 8y ago
    The difficulty of such interview questions doesn't stem from the problem of ensuring memory safety, but stuff like "finding the form of the recursion you need".
• TheCraiggers 8y ago
  An array?
• the_mitsuhiko 8y ago
  Hashmap or array :)
  • jandrese 8y ago
    Hard to imagine a hashmap is less complicated than a singly linked list under the hood.
    • joshuamorton 8y ago
      From a memory management perspective, a probing hashmap is just a vector/array. All of the bookkeeping is "safe" from a memory perspective.
    • the_mitsuhiko 8y ago
      A hashmap is in its simplest form just an array.
    • oconnor663 8y ago
      They're roughly equal if the singly-linked list is just a head pointer, because the "each object is only reachable through a single path, which owns it" property means the compiler can reason about what's going on. It's when you add a tail pointer (or go whole hog and make it doubly-linked) that you lose that property and have to use unsafe code (or heavyweight things like Arc<Mutex<...>>) to get the compiler off your back.
• baq 8y ago
  in comparison to a vector yes it's complex. it's recursive. it has pointers. algorithms to work with one aren't trivial and often are destructive.
• chewbacha 8y ago
  It's complicated because it's self-referential, not because it's conceptually complicated. Self-referential data structures in rust are more difficult because of the way ownership works. Of course, self-referential, mutating data structures are nefarious and hard to build in a thread-safe way. So the extra difficulty is actually an symptom of the inherit complexities of making them thread-safe.
• kevingadd 8y ago
  Lists, stacks, queues, hashtables. Maybe btrees.
• Jare 8y ago
  Anything that doesn't involve aliased pointers will be simpler from a safety perspective.