我在Rust中的链表实现不会在列表的末尾插入新元素

jv4diomz  于 2023-08-05  发布在  其他
关注(0)|答案(1)|浏览(126)

我正在Rust中实现链表数据结构,以尝试学习这门语言。我正在学习一个教程,但我注意到他们的实现只在链表的开始插入一个元素,而不是在它的结尾。我在网上搜索了其他实现,发现它们都做了同样的事情。因此,我开始制作我自己的insert()/add()fn版本。

type NodePointer<T> = Option<Box<ListNode<T>>>;

struct ListNode<T> {
    data: T,
    next: NodePointer<T>,
}

struct LinkedList<T> {
    head: NodePointer<T>,
}

impl<T: std::fmt::Debug> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    fn insert(&self, input: T) {
        let new_node = Some(Box::new(ListNode::<T> {
            data: input,
            next: None,
        }));

        let mut head = &self.head;
        loop {
            match head {
                Some(node) => {
                    println!("passing by {:?}", node.next.as_ref().unwrap().data);
                    head = &node.next;
                },
                None => {
                    head = &new_node;
                    println!("inserted {:?}", head.as_ref().unwrap().data);
                    break;
                }
            }
        }
    }

}

字符串
不知何故,每当我调用insert()时,我在循环外部初始化的head变量总是值None。有人能指出我做错了什么吗?

mw3dktmi

mw3dktmi1#

要改变列表,很可能需要在insert()函数中使用&mut self。事实上,它编译没有是一个大红旗,有什么是错误的。
您的错误是以下行:

head = &new_node;

字符串
这一行修改的是head变量,不是它所指向的!
你的意图可能是:

*head = new_node;


现在,突然之间,我们遇到了我已经说过的问题,如果self不可变,这是不可能的:

error[E0594]: cannot assign to `*head`, which is behind a `&` reference
  --> src\main.rs:33:21
   |
33 |                     *head = new_node;
   |                     ^^^^^ `head` is a `&` reference, so the data it refers to cannot be written
   |
help: consider changing this to be a mutable reference
   |
25 |         let mut head = &mut self.head;
   |                         +++


这可以通过将所有&引用更改为&mut引用来轻松解决。
另外,必须修复其中一个println
下面是最终的工作代码:

type NodePointer<T> = Option<Box<ListNode<T>>>;

#[derive(Debug)]
struct ListNode<T> {
    data: T,
    next: NodePointer<T>,
}

#[derive(Debug)]
struct LinkedList<T> {
    head: NodePointer<T>,
}

impl<T: std::fmt::Debug> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    fn insert(&mut self, input: T) {
        let new_node = Some(Box::new(ListNode::<T> {
            data: input,
            next: None,
        }));

        let mut head = &mut self.head;
        loop {
            match head {
                Some(node) => {
                    println!("passing by {:?}", node.as_ref().data);
                    head = &mut node.next;
                }
                None => {
                    *head = new_node;
                    println!("inserted {:?}", head.as_ref().unwrap().data);
                    break;
                }
            }
        }
    }
}

fn main() {
    let mut l = LinkedList::new();

    l.insert(42);
    println!("---");
    l.insert(69);
    println!("---");
    l.insert(420);
    println!("---");

    println!("{:#?}", l);
}
inserted 42
---
passing by 42
inserted 69
---
passing by 42
passing by 69
inserted 420
---
LinkedList {
    head: Some(
        ListNode {
            data: 42,
            next: Some(
                ListNode {
                    data: 69,
                    next: Some(
                        ListNode {
                            data: 420,
                            next: None,
                        },
                    ),
                },
            ),
        },
    ),
}

相关问题