Rust - memory management - pop ownership - linked list

Question

I thought I would have a go at a simple linked list. My working code follows.

I have two questions, with the List::pop() function below.

1. I could not get the program to work without the clone() statment. I am sure it must be possible to do this and sustain one owner of the item, (without resorting to unsafe mode). Any suggestions?

2. It is not clear to me that I have managed the heap memory associated with using the Box smart pointers. Do I actively need to do this, and if so, how do I do it?

// This implements a simple generic stack as a linked list.

use std::fmt::Display;
use std::fmt::Write;

type Link<T: Display + Clone> = Option<Box<Node<T>>>;

#[derive(Debug, Clone)]
struct Node<T: Display + Clone> {
    item: Box<T>,
    next: Link<T>,
}

impl<T: Display + Clone> Node<T> {
    pub fn new(item: T, next: Link<T>) -> Link<T> {
        Some(Box::new(Node{item: Box::new(item), next: next}))
    }

    pub fn append_to_string(&self, mut s: String) -> String {
        write!(s, "{}", *self.item);
        s
    }
}

#[derive(Debug, Clone)]
struct List<T: Display + Clone> {
    head: Link<T>,
    len: usize,
}

impl<T: Display + Clone> List<T> {
    pub fn new() -> Self {
        List{head: None, len: 0_usize}
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn push(&mut self, item: T) {
        let mut new = Node::new(item, self.head.take());
        self.head = new;
        self.len += 1;
    }

    pub fn pop(&mut self) -> Result<T, &str> {
        let current = &mut self.head;
        match current {
            None => Err("The List is empty."),
            Some(node) => {
                let item = *node.item.clone();  // The clone kludge
                *current = node.next.take();  // drop the popped node
                // Nagging question: is the old node
                // [box memory on the heap]
                // cleaned up - or do I need to do it?
                self.len -= 1;  // decrement the length
                Ok(item)
            },
        }
    } 

    pub fn print(&self) {
        let mut s =  String::from("The list: (");
        let mut p = &self.head;
        let mut virgin = true;
        while let Some(box_node) = p {
            s += if !virgin {", "} else {""};
            s = box_node.append_to_string(s);
            virgin = false;
            p = &box_node.next;
        }
        s += ")";
        println!("{}", s)
    }
}

fn push(list: &mut List<i32>, from: i32, to:i32) {
    // push a few numbers onto a list of type List<i32>

    for n in from..to {
        list.push(n);
        println!("Pushed: {}", n);
    }
}    

fn main() {
    // Test: construct a list of i32, push and pop some numbers

    let mut list: List<i32> = List::new();

    push(&mut list, 1, 4);
    list.print();
    loop {
        match list.pop() {
            Ok(result) => println!("Popped: {}", result),
            Err(message) => {
                println!("Error while trying to pop: {}", message);
                break;
            },
        }
    }
    list.print();
    push(&mut list, 1001, 1006);;
    println!("Length: {}", list.len());
    list.print();
}

Answer 1

And today I thought I would have a go at a simple linked list.

Because of ownership, linked lists are a non-trivial topic in Rust, and an absolutely terrible way to learn the language as far as I'm concerned. But if that is what you want there is an extensive guide called Learn Rust With Entirely Too Many Linked Lists, which covers both the reasonably simple linked lists and the much more complicated doubly linked lists.

Anyway

I could not get the program to work without the clone() statment. I am sure it must be possible to do this and sustain one owner of the item, (without resorting to unsafe mode). Any suggestions?

It's absolutely possible through the understanding and careful application (as they create odd transient states, and thus it's important to ensure no panic happens until proper state is restored) of the std::mem family of functions std::mem::swap and the "convenience wrappers" std::mem::replace and std::mem::take:

pub fn pop(&mut self) -> Result<T, &str> {
    let node = std::mem::take(&mut self.head).ok_or("The list is empty.")?;
    self.head = node.next;
    self.len -= 1;
    Ok(*node.item)
}

It is not clear to me that I have managed the heap memory associated with using the Box smart pointers. Do I actively need to do this, and if so, how do I do it?

You don't need to do anything, if a Box has not been consumed it will be dropped implicitly when it goes out of scope.

Incidentally from a stylistic perspective your code is way over-constrained, unnecessarily so:

• trait constraints are not usually set on types unless absolutely necessary, which is not the case here
• you should have as little methods behind impl bounds as necessary, in your list impl only print needs T: Display, so rather than have everything in an impl<T: Display> block you should have print alone in such a block, and every other method in an unconstrained impl <T> block, because they don't care about T being display.