How to implement `push_back()` function on LinkedList?

Question

I have started learning rust a few days ago. I had heard that implementing Data Structures in rust are pretty confusable though I wanted to give it a try. The choice fell on the simplest LinkedList.

I implemented a Node as a struct:

#[derive(Debug, Clone)]
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

Without a generic value, for simplicity.

I implemented fmt::Display in order to write tests, and a simple new function for node creation.

impl fmt::Display for Node {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

impl Node {
    fn new(value: i32) -> Node {
        Node {
            value,
            next: None,
        }
    }
}

Then I created a LinkedList struct that holds the head and the tail.

struct LinkedList {
    head: Option<Box<Node>>,
    tail: Option<Box<Node>>,
}

For now, I only tried to implement push_back() function and it turned out to be hard enough for me to fail.

It is the current state of it:

impl LinkedList {
    pub fn push_back(&mut self, value: i32) {
        let new_node = Box::new(Node::new(value));

        match self.tail {
            Some(ref mut tail) => {
                tail.next = Some(new_node.clone());
                swap(&mut Some(new_node.clone()), &mut self.tail);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node.clone());
            }
        }
    }
}

Before I show the results of it, let me explain how do I understand my code - which is where most likely the error occurs.

I create an immutable pointer to the newly created node. Pointer - Box - is stored on the stack and points to the node created on the heap.

Then I match self.tail to see if the list is empty. In such a case I execute this block of code:

self.head = Some(new_node.clone());
self.tail = Some(new_node.clone());

So I'm deluding myself that self.head and self.tail points to the same address on the heap, because I only clone the pointer. If I understand my debugger properly, it - unfortunately - ain't the case.

If I naively execute it on the empty list, it compiles and assigns some Node to the tail. When I try to add another node, the first arm executes:

tail.next = Some(new_node.clone());
swap(&mut Some(new_node.clone()), &mut self.tail);

Here, I want to operate on the tail, which should be the exact same node as the head, and modify its next property. Afterward, I try to swap the current tail, with the newly created node.

Thus, on this state, I would expect my LinkedList to look like that:

Head: Node { value: 5, next: Node { value: 3, next: None } }
Tail: Node { value: 3, next: None }

My code doesn't meet my expectations though.

It outputs:

Head: Node { value: 5, next: None }
Tail: Node { value: 3, next: None }

What do I misunderstand? I'd be grateful for any hints.

If someone wants to reproduce the code, I also share the code I wrote that is responsible for tests.

fn scan_list(list: &LinkedList) -> impl Iterator<Item=Node> {
    let mut current_node = list.head.clone();

    std::iter::from_fn(move || {
        match current_node.clone() {
            None => {
                None
            }
            Some(node) => {
                current_node = node.clone().next;
                Some(node.as_ref().clone())
            }
        }
    })
}

tests.rs

#[cfg(test)]
mod tests {
    use super::*;
    use expect_test::{expect, Expect};
    use crate::{scan_list, LinkedList, Node};

    fn test_list(src: &LinkedList, expect: Expect) {
        let actual: String = scan_list(src).map(|node| format!("{:?}\n", node)).collect();
        expect.assert_eq(&actual)
    }

    #[test]
    fn test_empty_list() {
        let list = LinkedList { head: None, tail: None };
        test_list(
            &list,
            expect![r#""#],
        )
    }

    #[test]
    fn test_list_with_single_node() {
        let list = LinkedList { head: Some(Box::new(Node::new(5))), tail: None };
        test_list(
            &list,
            expect![r#"
                 Node { value: 5, next: None }
            "#],
        )
    }

    #[test]
    fn test_list_with_two_nodes() {
        let mut list = LinkedList { head: None, tail: None };
        list.push_back(5);
        list.push_back(3);
        test_list(
            &list,
            expect![r#"
                 Node { value: 5, next: Node { value: 3, next: None } }
                 Node { value: 3, next: None }
            "#],
        )
    }

}

It of course doesn't pass the last one.

Answer 1

Box is a smart pointer. When you clone a Box, it creates a deep copy, not a shallow copy, and the nodes will be entirely different in memory (the implementation is here, if you want to take a look).

Moreover, what you are trying to do is impossible in Rust. You're trying to violate Rust's core borrowing rule: there are no aliasing mutable borrows. You try to alias head with tail when the list is empty, and tail with tail_prev.next when not. I guess you started with a simple code without all those clones, but the compiler complained so you added them. You just hid the problem, but solved nothing.

There are three different approach to solve that. The first and most recommended for you is to stop trying to fool the compiler. Just don't alias. Create a singly-linked-list with only head and no tail. This is something you should be able to solve on your own.

The second and third are more complex. The first of them being to use Rc and RefCell. The last and most dangerous is to use unsafe code (this is what std::collections::LinkedList does, but it is not recommended for beginners, especially without advice).

A very recommended reading if you want to create linked lists to learn Rust is Learn Rust With Entirely Too Many Linked Lists. It implements all the three variants and more.