My linked list implementation in Rust won't insert a new element at the end of the list

Question

I am implementing the linked list data structure in Rust to try and learn the language. I was following a tutorial, but I noticed that their implementation inserted an element only at the start of a linked list, and not at its end. I searched for other implementations online and found they all did the same thing. So I set out to make my own version of the 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;
                }
            }
        }
    }

}

Somehow, whenever I call insert(), the head variable I initialize outside the loop always has the value None. Can someone please point out what I am doing wrong?

Answer 1

To mutate your list, it is very likely that you will need &mut self in your insert() function. The fact that it compiles without is a big red flag that something is wrong.

Your mistake is the following line:

head = &new_node;

This line modifies the head variable, not what it points at!

What you probably intended is:

*head = new_node;

Now, all in a sudden, we do get the problem which I already talked about, that this isn't possible without having self be mutable:

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

This can easily be solved by changing all & references to &mut references.

Also, one of the printlns had to be fixed.

Here is the final working code:

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,
                        },
                    ),
                },
            ),
        },
    ),
}