How to make rust usable in schools

Programming courses for me became available in 8th grade (age: ~13 years) and IMO, starting much earlier wouldn't be a good idea, anyway. We had some general computer courses in 5th/6th grade, but those didn't involve programming.

Maybe, with visual programming, you could start earlier and lower the entrance barrier, but I only see the latter purpose as helpful. People still have to finish their special education (~3 years) after high school to be able to get a job as a developer.

That being said, different countries = different rules. I can only speak for my own experience in Germany/Berlin, not for anyone else and especially not for anyone outside Germany.

Time for me to slowly get back to the original topic: Rust has a steep learning curve, because it is a very pedantic and flexible programming language. There are so many ways to solve bigger problems, it's intimidating.

Also, please, never ever teach anyone how to make a linked list with Rust in their first year of programming. That'd be crazy. You can do that with GC languages, instead.

It's generally a good idea to show off several languages, that each have their own strengths and weaknesses. Just use another language that suits your needs, if you think the language is lacking in something. That's just natural, since all languages have trade-offs. There is no single programming language to rule them all.

It's not clear to me why anyone would want to teach high schoolers about linked lists in their first steps in programming. As I described above in my first years of programming we never heard of such things. Our programming tasks were related to the maths/physics we were doing at the time.

On the other, the other day I found I had knocked up a directed acyclic graph in Rust, as used in the old Hunt the Wumpus Game, and it was dead easy. All my nodes were are in a vector and all the links are just indices. No problem. I would expect teenage beginners to programming to grasp that pretty easily. No more difficult that doing same in Python or whatever.


Perhaps when we discuss "linked lists" in Rust we should distinguish between "pointer-based linked lists", which in Rust require very advanced skill and are fraught with potential UB, and "index-based link lists" (e.g., indexing into a Vec used as arena storage), which are trivial in Rust.

Or, there's the good ol' singly linked list, which is trivial to implement in Rust safely (Option<Box<Node>>).


The linked list, as a concept, is independent of how one actually realizes it.

And what is the conceptual difference between "pointer based" and "index based"?

After all, memory is just a big array, and pointers are just indices into that array.

The kind of indexes represented by Rust's raw pointers are not bounds-checked though :slight_smile: Hence, raw pointers are hard to use correctly, they have a potential of resulting in UB. The difference here is not conceptual any more – it's purely practical.


I'd say the differences are asymptotic runtime behavior as well as cache locality due to the way they're allocated.
A real linked list has each node allocated when consed to that list. So adding an element requires allocating. In addition, consing to or removing from the front is O(1), adding to or removing from the back is O(n) because you need to traverse the list to find its end.

In contrast, an index/arena based list isn't a linked list at all, it's a vec in terms of characteristics. Adding to or removing from the front is O(n) because pre-existing elements need to be moved, removing from the back is O(1) and assuming the arena is large enough, so is adding to the back. And oherwise it is O(n).

It is, but how you divvy up that array can matter quite a bit.

I currently teach to my students python for algorithms and oCaml for functional programming. This is why I think rust can be a good choice because of his functional and imperative nature. Rust is simple and practical compared to other multiparadigm alternatives. My students have between 15 and 18. So only having one langage for them to learn would be a good thing! They are very confused when I start to teach them oCaml. They try to think in python which is not possible in oCaml.

1 Like

Yeah, I think that the number model of Rust is simply designed better for actually controlling the CPU than thinking in more abstract number and math terms. Still, this could be a good place for a crate to fill in and make numbers more "virtual" and just try to make them work as much like you would expect from a math perspective. Maybe there could be a macro like expr! that allows you to put in math expressions and it will handle the numbers more naturally. For example:

assert_eq!(expr!(3.2 + 5), 8.2);

And in this case it wouldn't complain that you can't add an f32 and an i32.

My claim is that the notion of a linked list is about a set of items (nodes) that refer to other similar items (links) in such a way as to form a chain of linked nodes (list). It's about how one indicates the end of that chain. It's about how one, algorithmically, extends that chain or inserts new nodes in the middle or removes nodes, etc.

As such the linked list, conceptually, is nothing to do with "cons" and "cdr". It has nothing to do with memory addresses, raw pointers, array indices etc. They are just a means of implementing the notion of a linked list. A linked list could as well be a bunch of objects in a JSON document, a bunch of hyperlinked web pages or a pile of rocks with numbers on them!

That is just cruel :slight_smile:

Nothing need be moved when implementing a linked list vector/array. If you are inserting at the front by moving all the elements up then you have not implemented a linked list. In fact if you move all the elements in the array you have broken all the links as now all the elements contain the wrong index for their successor. As surely as moving all the nodes of a C style linked list around in memory, all the pointers become invalid.

In the simplest array based linked list new nodes are inserted, at the front, back or in the middle of the list by writing the new node into the next free array element and fixing up the head index or whatever node indices required to maintain the list. Removing nodes from from the list is just a matter of adjusting the head index or fiddling with successor link of a node.

Of course that "leaks" array elements as nodes are unlinked from the list. Fixing that is the subject of lesson 2 :slight_smile:


That's precisely what I said earlier. The arena-based version isn't a linked list at all, it's a Vec with another name.

1 Like

As nobody has posted code samples or detailed pseudocode, referring to “the arena-based version” is incorrect: There are many potential ways to implement a linked-style structure with an arena-style allocator, and each one will have different properties.

If you want to talk about some specific data structure, it’s probably best to provide some concrete description to ensure everyone is talking about the same thing.

I don't understand what you mean.

A linked list can live in an array/vector as a mess of elements containing indices as links to other elements as surely as it can exist in an memory space as structures containing memory addresses as links to other structs.

All the operations one does on linked lists, insertion, removal, etc can be done on a bunch of structs living in an array as much as any C style linked list formed of structs in malloc'ed memory.

One is just manipulating array indices within nodes rather than actual memory addresses.

Moving of nodes up and down the array is not required. No more than it is required to move malloc'ed nodes around in memory.

I feel that to insist a linked list is defined as being nodes linked by memory pointers is too limiting.


In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link ) to the next node in the sequence.


I hope we can end the discussion about linked lists in this thread and continue in a separate one one, if wanted. I did not mean to start an off-topic discussion by mentioning linked lists (btw, I meant a doubly-linked one, to clarify; as pointed out, a singly-linked list would not be too difficult to implement in Rust or too slow without unsafe)


I was referring to a data structure of which the properties I explicitly named. Please read a bit closer before answering to it.

Which I understood, which was the basis for my up-thread comment.

Edit: Corrected link to prior post.

Of course, you can teach whichever language you think suits your goals. But again, according to the statements of the creators of the language = it is NOT intended for teaching programming. Your choice - your responcibility

If anyone needs an example of arena based list they can use my version: components-arena. :slight_smile: I have used a singly linked circular list as an example in the README, but it doesn't matter: you can easely imagine an appropriated double linked list implementation.

It was requested we take the linked-list debate to another thread. So here it is: When is a linked list not a linked list?

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.