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

Question

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

Have you considered keeping track of the length as you push/pull items? Then your function simply becomes: `fn len(&self) -> usize { self.item_count }` ... ? This has the benefit of making your `len` function _much_ quicker. — Simon Whitehead, Jan 23 '17 at 01:44
Well, that would be way better perform-wise, but I'm not doing this for the performance, I wanted to know how I could do this by going through every node, if possible of course. — David Frickert, Jan 23 '17 at 01:47
@MatthieuM. Well, I was kind of unsure how to name it, it makes sense that the last element is the front yeah, I'll change it to push_front, thanks! — David Frickert, Jan 23 '17 at 20:04
@DavidFrickert: I've unfortunately seen many implementations of linked list with an "append" function, which involves walking to the end each time. Shortest way to quadratic complexity. — Matthieu M., Jan 24 '17 at 07:59

score 3 · Accepted Answer · edited May 23 '17 at 12:01

3

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.

edited May 23 '17 at 12:01

Community

1
1

answered Jan 23 '17 at 02:11

Shepmaster

388,571
95
1,107
1,366

1

That makes a lot of sense... I'm really dumb... It was actually not hard. I'll need to really understand references and borrowing and all that rust-specific behaviour. Since I come from Java I kind of miss those simple things. Thanks. – David Frickert Jan 23 '17 at 02:14
Actually, I partially read that, the beginning. But they don't implement a len() method, so that's why I kind of lost interest, but will do when I get better at grasping the basics! – David Frickert Jan 23 '17 at 02:17
4

@DavidFrickert yup, having to deal with some of these details takes some getting used to. However, after a little practice, you will find that these details fade into the background and help you think about your code (in all languages) a little bit better. – Shepmaster Jan 23 '17 at 02:17
@DavidFrickert in that case, there's no *need* to implement `len` because it would just be [`Iterator::count`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.count) on the `iter()` - by implementing an iterator, you get all those features for free. – Shepmaster Jan 23 '17 at 02:18
Oh, I did not know that, since `std::collections::LinkedList` has a `len()` I did not even consider that possibility. That should be quite useful. – David Frickert Jan 23 '17 at 02:22
@DavidFrickert of course, you could then implement `len` as `self.iter().count()` to provide a nicer API. – Shepmaster Jan 23 '17 at 02:26
2

Don't put yourself down; I struggled with C++ back then because of this pointers and `const` for the very same reason, it takes some time to line the dots. The good news is that after a while it's just intuitive. – Matthieu M. Jan 23 '17 at 10:51

score 3 · Answer 2 · answered Jan 23 '17 at 02:12

3

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.

answered Jan 23 '17 at 02:12

Josh Lee

171,072
38
269
275

Yeah I see that makes sense, I probably was kind of trying all the stuff possible to make it work and I didn't even realise it was so simple... Thanks! – David Frickert Jan 23 '17 at 02:15

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

2 Answers2