CODEWITHSUNDEEP
rust
David Frickert
David Frickert

Reputation: 127

How can I implement a len() function for linked list?

I implemented some basic linked list operations:

use std::mem;

//Generic List
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}
struct Node<T> {
    element: T,
    next: Option<Box<Node<T>>>,
}

//List functions
impl<T> LinkedList<T> {
    //Create empty list
    fn new() -> LinkedList<T> {
        LinkedList { head: None }
    }

    //push element
    fn push_back(&mut self, t: T) {
        let new_node = Box::new(Node {
            element: t,
            next: mem::replace(&mut self.head, None),
        });

        self.head = Some(new_node);

    }
}

I could not implement a len method:

//length calculator
fn len(&self) -> usize {
    let ref mut list = self.head;
    let mut count = 0;

    while let &mut Some(ref rest) = list {
        count += 1;
        list = &mut rest.next;
    }
    count
}

My idea was to loop while I could be sure I had a Some, and stop when I had a None in my variable list.

Though this doesn't work, I can't make a mutable reference to a non-mutable variable, and apparently I can't re-assign the list variable:

error: cannot borrow immutable field `self.head` as mutable
  --> 8_generics.rs:54:13
   |
54 |         let ref mut list = self.head;
   |             ^^^^^^^^^^^^

error: cannot borrow immutable field `rest.next` as mutable
  --> 8_generics.rs:59:25
   |
59 |             list = &mut rest.next;
   |                         ^^^^^^^^^

error[E0506]: cannot assign to `list` because it is borrowed
  --> 8_generics.rs:59:13
   |
 57|         while let &mut Some(ref rest) = list {
   |                             -------- borrow of `list` occurs here
58 |             count += 1;
59 |             list = &mut rest.next;
|             ^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `list` occurs     here

error[E0384]: re-assignment of immutable variable `list`
  --> 8_generics.rs:59:13
   |
54 |         let ref mut list = self.head;
   |             ------------ first assignment to `list`
...
59 |             list = &mut rest.next;
   |             ^^^^^^^^^^^^^^^^^^^^^ re-assignment of immutable variable

Upvotes: 0

Views: 940

Answers (2)

Shepmaster
Shepmaster

Reputation: 431669

You appear to be confusing a mutable variable binding with a mutable reference. I'd recommend reading What's the difference in `mut` before a variable name and after the `:`?

In short, you do not want any mutable references to the list here; you are not modifying the list. You do need to be able to mutate the variable holding the immutable reference to the head of the list.

fn len(&self) -> usize {
    let mut list = &self.head;
    let mut count = 0;

    while let Some(ref rest) = *list {
        count += 1;
        list = &rest.next;
    }

    count
}

I'd also recommend reading Learning Rust With Entirely Too Many Linked Lists.

Upvotes: 3

Josh Lee
Josh Lee

Reputation: 177715

Use a mutable local variable (not a mutable borrow):

let mut list = &self.head;
while let Some(ref rest) = *list {
    count += 1;
    list = &rest.next;
}

Here we need the binding to be mutable (let mut), not the data (&mut). See Mutability.

Upvotes: 3

Related Questions