So far I've only managed to right up chapter 1, but it's already ~6000 words, so probably worth checking out!
Chapter 2 is out: An Ok Singly-Linked Stack
6 Likes
Thanks for the effort! 
Much appreciated.
This is great, thank you!
I have a friend who is learning Java at uni and has been tasked to make various different naive linked list implementations, because of course that's what new cs students need to learn to do. Sorely tempted to point them at (at least the first pages of) this, it's an incredibly good read and just so good. Thank you for taking the time to do this.
2 Likes
Any plans for doubly-linked lists?
Yes, linked lists are planned (see the TOC for planned chapters). I got distracted with landing TARPL and rustcamp.
Very interesting, thank you !
I'll be there too! I'm really excited about all of the talks. They seem really interesting.
Edit: at RustCamp
New chapters!!!!
A Bad But Safe Doubly Linked Deque: A Bad but Safe Doubly-Linked Deque
An Unsafe Singly Linked Queue: An Unsafe Singly-Linked Queue
Two more chapters to go!
6 Likes
Gankro, let me tell you that your book is excellent. You explain everything step by step so I can understand everything (at least what I can learn to first). It's definitely one of the best practical tutorial that Rust has.
Thank you.
1 Like
This tutorial convinced me to believe that linked lists are the worst of all data structures!
Jokes beside, this is a really great and well written tutorial where one can learn the basics as well as how to use more sophisticated features of Rust. 
for @Gankra
I'd love to read a chapter about intrusive lists and unmovable data structures 
2 Likes
This is a guided tour of having the compiler scream at us.
Made me smile
Love the style it's written in, it's entertaining, but not obstructively so. Kinda reminds me of reading Learn You a Haskell or Learn You Some Erlang.
Thanks for this!
1 Like
This is really cool. The kind of resource that can help someone to get acquanted with a new language when coming from a CS background.
Is there a github repo for the book? Then the community could help out a bit.
There is, but pull requests won't be honored. The author had no more time for this apparently.
1 Like
See this twitter thread for a potential change to that situation.
Maybe this is obvious, but, the chapter on unsafe single linked list states:
`http://cglab.ca/~abeinges/blah/too-many-lists/book/fifth-basics.html
we're just going to grab a *mut Node to the insides of the Box right away. We know we can soundly do this because the contents of a Box has a stable address, even if we move the Box around. Of course, this isn't safe, because if we just drop the Box we'll have a pointer to freed memory.
However, it appears that at this point we have (1) a mut pointer to the contents of the Box node and (2) a mutable pointer inside of Box to its contents (maybe I'm misunderstanding the source from a quick glance). Is this accurate? If so, why is this legal?
Thanks
You can think of it like that, yeah. There’s the raw mut ptr to the Node created inside push() and the Box itself has a ptr to its contents (via the Unique wrapper).
Derefe’ing a Box gets you a shared or unique (depending on context) reference to its contents. A reference is just a borrow-checked pointer. So then you also have a mutable ptr stored inside the Box and then a shared or unique ptr (really reference but it’s essentially the same thing for our purpose here) elsewhere.
So having two ptrs exist in memory at the same time isn’t an issue on its own - the safety/legality comes into play when you start doing read/write operations through the pointer. Under normal borrow conditions, if you obtain a &mut from the Box, then no more shared or unique borrows can be taken out while that &mut is still active - compiler enforces this. You also cannot move the Box until all borrows of it (or its content) are gone - this is also compiler checked. This latter bit is what the code there is sidestepping, and its able to get away with it because of the stable address aspect.
You can also consider how mutable reborrow works. This is a case where some code has a &mut and then another piece of code borrows it temporarily (ie reborrow) - while the reborrow is active, the original &mut is frozen: no reads or writes through it. But, it exists in memory. When the reborrow ends, the original &mut becomes active again and can read/write the value. The compiler verifies all of this. The key part is that a read/write happens through a unique path to the value in this case. The path may change (eg when a reborrow is done) but there’s a unique one at any given point in time. When you use raw ptrs, you need to ensure the same thing manually.
This is a somewhat subtle and nuanced topic though. At some point, Rust will likely gain a formal memory model, at which point I suspect these interactions and aspects will be defined a bit more formally and/or comprehensively.
2 Likes
Maybe considering also https://crates.io/crates/seq, a Functional-Programming-Alike Sequence implementation, which allows to manage dynamic lists/sequences on Stack performing recursive calls (self-appraisal)