1. 27

  2. 5

    This is a classic. It’s a surprise to many people trying to learn Rust that such a CS 101 data structure hits Rust’s blind spot, and ends up being absolutely the worst way to learn Rust (as this article makes it clear).

    1. 5

      One of the points this article makes is that linked lists are overrated and perhaps shouldn’t be a “CS 101” data structure to begin with.

      1. 4

        Analogy time! Basic math vs basic CS (grade school/high school level).

        Most people don’t use long division after school. But it’s still seen as a fundamental part of teaching arithmetic.

        In analogy, linked lists are a basic part of basic CS. They’ve been around forever, there’s oodles of material, and they can be reasoned about easily. The linked article even says so!

        They’re simple and great for teaching!

        Well, yeah. You’re reading a book dedicated to that premise. Well, singly-linked lists are pretty simple. Doubly-linked lists can get kinda gnarly, as we’ll see.

        I implemented linked lists in Pascal back in the day. I’m sure people are using Python to do so now. If they’re not simple to implement in Rust, that’s fine. Rust is not a good language for introductory programming anyway.

        It’s important to distinguish “linked list, the simple pedagogical tool” from “linked list, fundamental building block in a system”. Nowadays the second choice is probably not optimal.

        Edit added sentence.

        1. 3

          Linked lists are a good way for programmers in mid-level languages (C, C++, Pascal) to learn to juggle pointers and “navigate” a data structure built with pointers, which means they’re a good way to introduce data structures beyond fixed-size buffers which don’t require that much more code.

          They’re also implicitly present in other contexts. Activation records? Singly-linked lists. Object hierarchies without multiple inheritance? Singly-linked lists. There’s a subtle power to having even one pointer per object.

      2. 4

        C and C++ give us a clear example what happens if you just let people take pointers to random data on the stack: pervasive unmanageable unsafety.

        I feel like this doesn’t actually happen very often. Something like what the author describes here would look like

        foo (int **bar)
            int baz = 3;
            *bar = &baz;
            int *bar;
            printf("%d\n", *bar);

        which is seriously unidiomatic C. I think I’ve chased malloc-related bugs much more than stack-related bugs. Now, having the compiler catch the above case is nice, but it’s far from the most motivating example for rust’s system.

        1. 2

          I’ve chased malloc-related bugs much more than stack-related bugs

          I think that’s related. Coding patterns and APIs that would extensively use on-stack data more are risky, and therefore defensive coders avoid them.

          For example, in C if you were making a growable vector, you wouldn’t return in by value like

          struct vec make_vec();

          You’d return a vec* — a malloced struct instead, since that gives implementation privacy, object uniqueness, and avoids the headaches of accidental copies and pointers to on-stack structs.

          In contrast Rust’s Vec is a 3-word struct {ptr, len, capacity} returned and moved around by value. Use of Box<Vec> (equivalent of mallocing vec*) is considered an anti-pattern. That’s because the safety net of single ownership and borrowing makes a foolish design foolproof.

          1. 1

            I think your example is rather poor, since the ptr is allocated on the heap even if struct vec is passed by value.

            That said, I think the real reason is that stack variables only last for one block. This doesn’t matter to a borrow checker, but it sure does make it easier for us humans. Heap-allocated variables have a much greater potential for being alloc’d very far away from where they are free’d.

            1. 2

              push still takes a pointer to the on-stack Vec struct. But my point is you rarely run into problems with pointers to on-stack data, because you rarely use on-stack data for many reasons.

        2. 2

          I love how snarky this is. It may become my second favorite language tutorial, after The (Poignant) Guide To Ruby.

          1. 2

            Ahhh this reminds me of all the hoops I had to jump through to make a mutable computation graph for automatic differentiation in rust.

            I ended up just storing a reference to each parent in a node and wrapping the value of the derivative that I wanted to mutate in a RefCell and calling *t.derivative.borrow_mut() = d_dx.data after computing the derivative for a node

            Rust does (rightfully so) feel overly complicated and verbose at first, but the feeling of having the confidence that your compiled code will work (most of the time!) can’t be beat

            1. 2

              Ahhh this reminds me of all the hoops I had to jump through to make a mutable computation graph for automatic differentiation in rust.

              This sounds neat. Could you maybe explain it a bit more?

              1. 3

                Most likely it is referring to this submission yesterday.

            2. 1

              I’ve been studying (Common) Lisp lately, and how much easier this is there is hilarious. Of course, the language is somewhat based on linked lists.

              1. 3

                Right — LISP (in its classic forms at least) is literally a language whose only tool is a cons cell, so naturally everything looks like a linked list.