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

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.

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.

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!

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.

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.

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.

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

#!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

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.

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?

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)
    }
}

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.

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>;

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.