Need help with Simple Linked List

Programming Rust
1

I hope it’s okey to ask for help on exercises here as well; I am currently working on the LinkedList, and I cannot seem to get a hold of it. Here’s what I’ve got so far:

use std::iter::FromIterator;                                                                                                                                                                                                          [5/1974]

pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
    len: usize,
}

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    pub fn new(_element: T, next: &Option<Box<Node<T>>>) -> Self {
        Node {
            data: _element,
            next: None,
        }
    }
}

impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self
    {
        SimpleLinkedList {
            head: None,
            len: 0,
        }
    }

    pub fn is_empty(&self) -> bool {
        match self.head {
            None => true,
            _ => false,
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn push(&mut self, _element: T) {
        self.len += 1;
        self.head = Some(Box::new(Node::new(_element, &self.head)));
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            return None
        }

        self.len -= 1;

        let old_node = self.head.as_ref().unwrap();
        Some(old_node.data)
    }
// -- snip --

I am currently working on the pop-Function and I cannot seem to get it to work; the thing that I am wanting to do is, to access the data part of the head node and wrap it into an Option<T>, but no matter what I try, it just won’t let me access that data.

Latest error message says:

cannot move out of old_node.data which is behind a shared reference: move occurs because old_node.data has type T, which does not implement the Copy trait

I was also trying working with *, and working with &mut, etc. but I am not getting any closer.

What am I doing wrong here? It cannot be that hard to access that data? I also looked into Copy trait, but somehow I feel that this is growing out of hand and out of scope of the exercise?

2

You don’t need to Copy the data. pop() is supposed to remove the head (node), so you’ll be moving the value out (and returning it).

as_ref() converts a &Option to an Option<&T>. You don’t need to return a reference, you want to take the value, and replace your head with your head.next value, and return the head.data.

Hint for solution: look into the Option.take() function, which replaces Some(x) with None, returning the value of x.

3

@pygospa Just to be sure: do you understand the error message? That is, do you understands its reasoning, i.e. why this rule exists?

4

Well, that’s what I was actually trying to do:

  • Get the head-node to access the data + the reference to the next node.
  • Return the data
  • save the next node as head-node.

So to do that I’d first need to get to the data and save it, before I can throw the old head node away, and replace it with the next node. And I cannot just return the old node, because the signature says that the function will return Option<T>, and the Node itself is a Option<Box<Node<T>>>. That is why I am trying to drill down to that T and wrap it in Some().

I guess I am thinking too procedural here; I checked out take(), and that’s probably what I want.

Thanks for the question. I do believe so, but maybe it helps me, to try to explain it (and maybe I am misunderstanding things):

My understanding is, that when assigning a value to a new variable, the old variable “moves” the ownership to the new variable, and in every point in time there can be only one owner of things. This can be circumvented either by borrowing (which will leave the ownership where it is, but can still access the data for reading (and with &mut even for writing - but that only once) or by copying (which will create a new and separate instance, i.e. copying values to a new place in memory).

The Error tells me that it’s impossible to copy the data (due to the missing Copy trait), so it is trying to move the ownership; I could of course limit the type variable T to types that implement Copying (where T: Copy), but that doesn’t feel right; plus I actually don’t want to copy that value anyways - I want to move it to the caller of the function (at least that’s my understanding of what a return value from a function does).

Rust tells me that it does not allow moving, because of other references (and I think this has to do with lifetimes, i.e. the compiler checks lifelines during creation of the references to make sure the references don’t outlive the data they are pointing to), and that’s why I cannot do the move. What I don’t understand, though is where exactly my data is being referenced elsewhere? This should only be held by SimpleLinkedList.head? So I am not really sure why I cannot transfer the ownership at this point (and if take() will work, then I am even less sure why that’s okey and the above code isn’t?!).

To my understanding, the as_ref() should circumvent the movement, i.e. instead of moving this should now be borrowed instead. But that’s not happening either, and I am not sure why this is not allowed, either.

5

@pygospa I haven’t read your reply yet – will do right after sending this – but I figured you might want to read Learning Rust With Entirely Too Many Linked Lists anyway.

It uses mem::replace, but you can use Option::take instead in at least some all cases.

6

I prefer the mentoring UI to help on specific exercises, feel free to open a request and ping me with the link. Option::take and as_ref should get the job done, but it can be instructive to talk about the details of specific error messages along the way.

7

Thank you for the resource - I actually stumbled upon it, when trying to figure out what I was doing wrong, but only took a small glance at it, and then steerd away, because I felt like cheating :sweat_smile:

After your suggestion I read the Chapters 1-4, and I have to say it is quite a good read and resource - I am for sure finishing the read. But after the first four chapters I felt confident enough to take another try at the exercise. Because @senekor asked, I created a private mentoring - if anyone likes to take a peek. But I think the code is fine now (still any feedback is highly appreciated).

There are two more points:

  1. The tutorial on the Lists suggests implementing the following (in this chapter: Drop - Learning Rust With Entirely Too Many Linked Lists):
impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
        }
    }
}

To be quite honest I don’t get that; to my understanding, because of all the ownership, borrowing, and lifelines why would I still need to take care of writing a method to clean up the memory? I would have expected Rust to be able to do this without me worrying about it - I mean what’s the point of all the hassle when in the end, you still end up cleaning memory yourself?

  1. To correct myself from above:

pop(&mut self) declares self mutable, therefore only one reference may exist, AND (and that’s what I did not know) - when borrowing a value, one cannot move it. That is why I couldn’t do let old_node = self.head.unwrap(), because that would move self.head which is part of the borrowed self. Now I did find a way to get to that data with as_ref(), but as the name suggest, that only creates an unmutable borrow. Some(old_node.data) would again create a move, and that’s impossible to do.

I hope I now understood this correctly. It’s funny that for a mutable object you can change it, but you cannot empty it, and then fill it with something else - it just didn’t occur to me that that’s the problem, but thinking about it, only makes it consistent. The workaround with a function that replaces and returns the value “at the same time” is really weird as well, but I do get it. And I finally understand how .take() works, and why you can work with .map() on an Option as well. In that sense, Rust is not as consistent as I would have thought it to be - this is a lot of syntactical sugar that feels weird because it looks the same as e.g. .map() on an iterator (but works differently). A lot of implicite knowledge you need to have.

Well. For now my Rust journey ends - it was a bumpy ride and stole a lot of time for the Analytical April. But it really got me intreagued, and I hope to find time to continue with the exercises for the Rust track every now and then. Thanks to all who mentored me and helped me :slight_smile: I really learned a lot.

8

I’m missing the inconsistency. Can you point at it more directly?

It seems plausible you mean something else than what syntactic sugar is commonly understood to mean, namely syntactic forms that are nicer to read/write but that are strictly superfluous from a semantics viewpoint. If you do mean this, then I need some more elaboration or concrete examples to be able to understand.

Either way, you might like this blog post: Rust's Ugly Syntax

9

I mean something like .map(). Map takes a closure and applies it to every value of an iterator and returns an iterator with the new values. So I expect it to always take something that’s some kind of collection (Vector, List, Arrays, etc.) and return a bunch of transformed values that are transformed exactly the way described in the closure.

But that’s not true for Option. Option is not a collection of values, Option is either Some(x) or None. Different to my vec.iter().map() I don’t call option.iter().map() - I can call option.map() directly - which to me is the first inconsistency (and I would never have guessed to do this, nor did I at first understand the solutions I saw that did this). And then, the closure is not applied to None, just to Some(x) - and in case of Some(x) the closure itself only applies to the x - so option.map(|x| x*2) does something totally different than (0..10).map(|x| x*2) - and then it even does not return something iterable that I need to collect or store in an iter variable; but actually an Option.

That’s what I mean with inconsistency; (0..10).map(|x| x*2) works like you’d expect a map to work; option.map() is somewhat “syntactical sugar” for a match option {None => None, Some(x) => ... }.

And I am not saying that this is an entirely bad thing; but for me it’s a greater burden to understanding the language…

I hope that makes it clearer, what I mean?

10

Yes, that helped a lot!

There are many individual map functions. They share the same name through convention only.

(Likewise, there are many iters, for the same reasons.)

Note: for many of these structures you do not .map on that exact structure, but on some Iter struct instead.

You probably also expect the .map to be structure-preserving: when given a Some it will produce a Some and never a None, and when given 56 Vec elements you expect .map to produce 56 transformed elements, in order.

Yeah it is. If it isn’t, then surely Vec and your SimpleLinkedList aren’t collections either, for they too can be empty.

Haskell syntax perhaps helps bring out the similarity between Option and SimpleLinkedList:

-- I promise this corresponds to the Rust code
data Option a = None  | Some a
data SLList a = Empty | Node a (SLList a)

Except for some recursion they are the same!

Yes! Do note however that you can still call an .iter first: Option in std::option - Rust. The std::option::Iter struct offers a .map of its own as well.

A structure-preserving .map on e.g. a Vec would necessarily immediately produce an entire new Vec. This is rarely what you want. It is therefore that I suspect that many .iter-less .maps are missing.

I agree that this is somewhat inconsistent. However,

  • it is not a matter of syntax, and
  • it is not a matter of language design either, really, but rather of the problem domain: Option and Result do lend themselves to structure-preserving maps, but many other types do not. Luckily iterators do, hence all the .iter().map(...)s.

Rust’s maps have the same spirit as Haskell’s fmap. (They just can’t be unified formally because of Rust’s type system cannot express certain types.)

Note that other types have this because you .map over Iter structs instead over the original structures themselves. You put an Iter in and you get one back. Just like with Option you put in an Option and get one back.

Aye, this is literally what it means.

This is not commonly called syntactic sugar because map itself is not a syntactical construct: map is just an identifier, same as mop.

11

The section in the book does explain that:

When list gets dropped, it will try to drop A, which will try to drop B, which will try to drop C. Some of you might rightly be getting nervous. This is recursive code, and recursive code can blow the stack!

Basically, the default Drop implementation can cause a stack overflow.