Learn Rust by writing Entirely Too Many linked lists

Overview

Learn Rust by writing Entirely Too Many Linked Lists

Build Status

Read the pretty version at https://rust-unofficial.github.io/too-many-lists/.

Building

Building requires mdbook, which can be installed from crates.io:

cargo install mdbook

Assuming you've placed the install directory ~/.cargo/bin into your system PATH, then run from the root of your local copy:

mdbook build

If you'd prefer, this project can also be built with GitBook, although GitBook is not officially supported and compatibility is therefore uncertain and incidental.

Comments
  • it assumes cargo new makes a lib but it makes a bin

    it assumes cargo new makes a lib but it makes a bin

    On the first page, the first instructions are cargo new lists cd lists

    cargo new by default makes a bin, not a lib. The beginning of chapter 2 seems to indicate a lib was expected here.

    I propose to change the above code in chapter 1 to include --lib

    opened by robinderksen 10
  • Explain `&**node`

    Explain `&**node`

    From https://www.reddit.com/r/rust/comments/3geb5q/learning_rust_with_entirely_too_many_linked_lists/ctxgwmz, maybe explain &**node to make it more obvious what is being dereferenced. Coming from C, this was a little confusing.

    opened by ericye16 10
  • Add instructions for rustbook build via mirror

    Add instructions for rustbook build via mirror

    Replaces old instructions of compiling rustc from scratch.

    Instead of compiling rustc, I've found a mirror of the rustbook code.

    Both rustbook and the book compile without problems on my Linux box: Arch Linux x86_64 (kernel 4.1.3-1-ARCH) rustc 1.3.0-nightly (4dfe7a16c 2015-07-30) cargo 0.4.0-nightly (e0a82d6 2015-07-29) (built 2015-07-30)

    I'm fairly certain most people will want to avoid bootstrapping the entire rustc compiler if the mirror works just as well.

    opened by jameslzhu 10
  • let can shadow name in same block???

    let can shadow name in same block???

    I was taken aback by this code in first.rs:

       Link::More(node) => {
                let node = *node;
                self.head = node.next;
                Some(node.elem)
            }
    

    which appears to be equivalent to:

            Some(node_box) => {
                let node = *node_box;
                self.head = node.next;
                Some(node.elem)
            }
    

    I tried to find something in the official Rust documentation to justify shadowing a name which is already in use in the block and didn't find anything. Can you point to somewhere which promises that this is stable? And maybe something should be said to explain this to newbies like me!

    P.S. I'm absolutely loving this tutorial, it's filling in key things I was missing!

    opened by GregDavidson 8
  • Deploy to GitHub pages

    Deploy to GitHub pages

    Some notable changes in this PR:

    • Use gh-pages for deploying this book (Close #103, close #39)
      • A demo is at https://lzutao.github.io/too-many-lists/.
      • Fix path for indy.gif: Close #95.
    • Use the same mdbook version as rust-lang/book.
      • Migrate to mdBook v0.2.1.
    • Change git settings:
      • Change git.depth to 1 (default 50).
      • Make git clone quiet.
    • Rename build stage:
      • Rename before_script stage to install.
      • Rename after_success stage to before_deploy.
    • No install Rust toolchain. Rationale: We don't test any Rust code, so we don't need to install rust toolchain. This would reduce waiting time for the real script to work.
    opened by tesuji 7
  • 2.5 Pop: Error 0382

    2.5 Pop: Error 0382 "value used after move"

    With rustc 1.27.0 (3eda71b00 2018-06-19), the final "idiomatic" example fails to compile. I found the following solution:

        pub fn pop(&mut self) -> Option<i32> {
            match mem::replace(&mut self.head, Link::Empty) {
                Link::Empty => None,
                Link::More(node) => {
                    let elem = node.elem;
                    self.head = node.next;
                    Some(elem)
                }
            }
        }
    

    However, as I am a Rust beginner, I have no idea how idiomatic this is.

    opened by jeeger 6
  • Add Travis CI config to release built HTML book on tag

    Add Travis CI config to release built HTML book on tag

    I think it is convenient to have an offline version of the book for download as well, so I wrote this Travis CI config to do that. With it Travis CI can take care of releasing a zip archive of the HTML book on tag. Creating a release on Github also triggers it to append the archive to the release.

    Of course, you need to go to Travis CI to enable it for this repo. It also requires env var GH_DEPLOY_TOKEN be filled with a Github personal access token with "public_repo" enabled. This can be set in the Settings tab in the Travis CI page of this repo.

    opened by louy2 6
  • mdbook: Replace deprecated book.json with book.toml

    mdbook: Replace deprecated book.json with book.toml

    mdbook warns when building:

    2019-01-11 16:56:51 [WARN] (mdbook::book): It appears you are still using book.json for configuration.
    2019-01-11 16:56:51 [WARN] (mdbook::book): This format is no longer used, so you should migrate to the
    2019-01-11 16:56:51 [WARN] (mdbook::book): book.toml format.
    2019-01-11 16:56:51 [WARN] (mdbook::book): Check the user guide for migration information:
    2019-01-11 16:56:51 [WARN] (mdbook::book):      https://rust-lang-nursery.github.io/mdBook/format/config.html
    2019-01-11 16:56:51 [INFO] (mdbook::book): Book building has started
    2019-01-11 16:56:51 [INFO] (mdbook::book): Running the html backend
    
    opened by tesuji 5
  • try_unwrap() has been stabilized on nightly

    try_unwrap() has been stabilized on nightly

    #!feature[rc_unique] is no longer necessary, since try_unwrap() has been stabilized. This effects the text in

    • fourth-breaking.md
    • fourth-peek.md

    and the source in

    • lib.rs
    opened by jtepe 5
  • cargo test error on rust 1.32.0 and 1.35.0

    cargo test error on rust 1.32.0 and 1.35.0

    rror[E0382]: use of moved value: node --> src/first.rs:36:22 | 35 | self.head = node.next; | --------- value moved here 36 | Some(node.elem) | ^^^^^^^^^ value used here after move | = note: move occurs because node.next has type first::Link, which does not implement the Copy trait

    error: aborting due to previous error

    For more information about this error, try rustc --explain E0382. error: Could not compile lists.

    opened by nkbai 4
  • Dropping

    Dropping

    I'm new to Rust, but I'm curious as to why we don't implement drop for the first two lists like this:

    fn drop(&mut self) { while let Some(_) = self.pop() {} }

    This seems like a very obvious implementation, and it seems more elegant than the given implementations. I ran a test which creates a list of a million elements and lets said list go out of scope, and everything went fine (the test resulted in stack overflow when I ran it before implementing drop).

    Is there some reason I'm not seeing to prefer the given implementations?

    opened by markcsaving 4
  • Fourth.rs note, and printing.

    Fourth.rs note, and printing.

    In fourth.rs, my cargo, (edition = "2018"), wants Node prev and next Boxed. It was not too hard to make it work. How about printing? Something like:

    impl<T: std::fmt::Display> fmt::Display for List<T> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            let mut rc_str = String::from("(");
    
            let mut cur_link = &self.head;
            let mut start = true;
    
            while let Some(boxed_node) = cur_link {
                if start {
                } else {
                    rc_str.push_str(", ");
                }
                start = false;
                rc_str.push_str(&format!("{}", boxed_node.elem));
                cur_link = &boxed_node.next;
            }
            rc_str.push_str(")");
    
            write!(f, "{}", rc_str)
        }
    }
    
    opened by X01XX 1
  • A note on history

    A note on history

    First of all, I agree with everything that's said in the introduction. However, linked lists are terrible data structures is an incomplete argument. Same with linked lists are as niche and vague of a data structure as a trie.

    There's a huge point that is not being taken into consideration about linked lists, one that I think would make the argument richer: history. All the points you noted are true for modern systems. Once I read The Art of Computer Programming, I came to realize that most slow and apparently bad algorithms and data structures are great under a specific set of assumptions. Linked lists were great at a time when the assumption CPU is slower than RAM was true, and cache wasn't a thing.

    We teach every undergrad how to write a linked list. Yes, because most courses are outdated. At the time they were encouraged, they were truly the best.

    opened by jlxip 0
  • In [7.2 Variance and Subtyping], we can add a simple function to prove that `LinkedList<T>` is covariant over `T`, and `type Link<T> = *mut Node<T>` is not like so

    In [7.2 Variance and Subtyping], we can add a simple function to prove that `LinkedList` is covariant over `T`, and `type Link = *mut Node` is not like so

    In 7.2 Variance and Subtyping , we can add a simple function to prove that LinkedList<T> is covariant over T.

    use too_many_linked_list::unsafe_deque::LinkedList;
    fn ensure_covariant<'long: 'short, 'short>(list_long: LinkedList<&'long i32>, mut list_short: LinkedList<&'short i32>) {
        let list_short_new: LinkedList<&'short i32> = list_long; // to prove `LinkedList<T>` is covariant over `T`
        //let list_long_new: LinkedList<&'long i32> = list_short; // to prove `LinkedList<T>` is contravariant over `T`
    }
    
    /// We can prove that `LinkedList<T>` is covariant over `T`.
    /// ```no_run
    /// # use too_many_linked_list::unsafe_deque::LinkedList;
    /// fn ensure_covariant<'long: 'short, 'short>(list_long: LinkedList<&'long i32>, mut list_short: LinkedList<&'short i32>) {
    ///     let list_short_new: LinkedList<&'short i32> = list_long; // to prove `LinkedList<T>` is covariant over `T`
    /// }
    /// ```
    type Link<T> = Option<NonNull<Node<T>>>;
    
    /// We cannot prove that `LinkedList<T>` is covariant over `T`, if we use `type Link<T> = *mut Node<T>;`
    /// ```compile_fail
    /// # use too_many_linked_list::unsafe_deque::ptr_mut::LinkedList;
    /// fn ensure_covariant<'long: 'short, 'short>(list_long: LinkedList<&'long i32>, mut list_short: LinkedList<&'short i32>) {
    ///     let list_short_new: LinkedList<&'short i32> = list_long; // to prove `LinkedList<T>` is covariant over `T`
    /// }
    /// ```
    /// compiler errors:
    ///    = note: requirement occurs because of the type `ptr_mut::LinkedList<&i32>`, which makes the generic argument `&i32` invariant
    ///    = note: the struct `ptr_mut::LinkedList<T>` is invariant over the parameter `T`
    type Link<T> = *mut Node<T>;
    
    opened by viruscamp 0
  • Reword description about struct-wrapping

    Reword description about struct-wrapping

    In the first-layout.md, there is a step where we convert List into a struct due to pub enum spilling its internals.

    I've had a hard time wrapping my head around this step, and I believe it would be much clearer to the readers what we're doing if we explicitly say that we're wrapping the previous List enum inside the new List struct.

    opened by puilp0502 0
Owner
Catch-all organization for unofficial Rust projects which have become orphaned or otherwise need community maintainership
null
Too lazy to read the full article? Skim it

SkimGPT When you're too lazy to either read the article or ask AI questions, you can use SkimGPT to help you. Install Clone this repo: git clone https

Huy 9 Apr 22, 2023
A tool to make grocery lists written in Rust

grusterylist: makes grocery lists, written in Rust grusterylist uses and can add to local libraries of user-added recipes and grocery items to put tog

null 3 Jun 17, 2022
Rust programs written entirely in Rust

mustang Programs written entirely in Rust Mustang is a system for building programs built entirely in Rust, meaning they do not depend on any part of

Dan Gohman 561 Dec 26, 2022
Tools for managing GitHub block lists

GitHub block list management Octocrabby is a small set of command-line tools and Octocrab extensions that are focused on managing block lists on GitHu

Travis Brown 97 Nov 3, 2022
Portable linked-list allocator designed for baremetal systems

Palloc Portable linked-list allocator for embedded / baremetal systems. Using the crate Include this in the [dependencies] section of Cargo.toml pallo

Pietro 3 Jan 11, 2022
Linked Atomic Random Insert Vector: a thread-safe, self-memory-managed vector with no guaranteed sequential insert.

Linked Atomic Random Insert Vector Lariv is a thread-safe, self-memory-managed vector with no guaranteed sequential insert. It internally uses a linke

Guillem Jara 8 Feb 1, 2023
Simple autoclicker written in Rust, to learn the Rust language.

RClicker is an autoclicker written in Rust, written to learn more about the Rust programming language. RClicker was was written by me to learn more ab

null 7 Nov 15, 2022
Learn to write Rust procedural macros [Rust Latam conference, Montevideo Uruguay, March 2019]

Rust Latam: procedural macros workshop This repo contains a selection of projects designed to learn to write Rust procedural macros — Rust code that g

David Tolnay 2.5k Dec 29, 2022
A repository for showcasing my knowledge of the Rust programming language, and continuing to learn the language.

Learning Rust I started learning the Rust programming language before using GitHub, but increased its usage afterwards. I have found it to be a fast a

Sean P. Myrick V19.1.7.2 2 Nov 8, 2022
Try to learn Rust in a week. The goal is to finish a quiz at the end of the week.

RustInAWeek Try to learn Rust in a week. The goal is to finish the quiz at the end of the week. Quiz link https://dtolnay.github.io/rust-quiz/1 Book l

null 1 Dec 13, 2021
LearnRustTogether - Let's learn Rust together

Curated collection of lists of useful resources to learn Rust together. List of forums and chats you may find here. I encourage you to seek for help i

Learn Together 3 Nov 29, 2022
Learn programming with Rust as a first language (book)

Learn programming with Rust as first language This is a book to learn programming from scratch. Read the book here: https://deavid.github.io/lprfl/ LI

David Martínez Martí 2 May 21, 2022
This Repo Contains my Week Long Journey Trying to Learn Rust Programming Language 🦀.

the-rust-way This Repo Contains my Week Long Journey Trying to Learn Rust Programming Language ?? . ?? Thanks to all Wonderful Contributors Thanks a l

Kanishk Pachauri 7 Oct 20, 2022
A console viewer for trees – pet project to help me learn Rust.

treeviewer This is a pet project to help me learn Rust. But maybe it’ll end up being of actual use for someone? The idea is to write a program that, g

Daniel Janus 3 Jul 15, 2023
Repository to learn fractal generation algorithms.

Fractalrs Created this project so I can study Rust while programming fractals! I have always wanted to learn fractal generation. Fractals Fractals are

Luke Dias 4 Jun 10, 2023
:crab: Small exercises to get you used to reading and writing Rust code!

rustlings ?? ❤️ Greetings and welcome to rustlings. This project contains small exercises to get you used to reading and writing Rust code. This inclu

The Rust Programming Language 33.1k Jan 2, 2023
A Rust macro for writing nested loop expressions

loop_chain A Rust macro for writing nested loop expressions Usage | Examples | Docs Dependencies [dependencies] loop_chain = "0.1.1" Usage For express

Takayuki Maeda 5 Jul 30, 2021
Take your first step in writing a compiler. Implemented in Rust.

first-step-rust Take your first step in writing a compiler, using Rust. Building from Source Make sure the Rust toolchain is installed on your compute

PKU Compiler Course 13 Aug 28, 2022
S-expression parsing and writing in Rust

rsexp S-expression parsing and writing in Rust using nom parser combinators. This implemantion aims at being compatible with OCaml's sexplib. The main

Laurent Mazare 12 Oct 18, 2022