rust - 如何为链表实现 len() 函数？

Question

我实现了一些基本的链表操作:

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

    }
}        

我无法实现 len 方法:

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

我的想法是当我确定我有一个Some时循环，当我的变量list中有一个None时停止.

虽然这行不通，但我无法对不可变变量进行可变引用，而且显然我无法重新分配列表变量:

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

Answer 1

您似乎将可变变量绑定(bind) 与可变引用 混淆了。我建议阅读 What's the difference in `mut` before a variable name and after the `:`?

简而言之，您不希望对此处的列表有任何可变引用；您没有修改列表。您确实需要能够改变保存对列表头部的不可变引用的变量。

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
}

我还建议阅读 Learning Rust With Entirely Too Many Linked Lists .