LinkedList push_front method


#1

i am continuing learning rust and as an exersise i decided to make a linked list. Lets make it as a enum:

pub enum List {
EmptyNode,
Node { element: T, next: Box<List> }
}

The question is in adding elements into this list.
How can i make a push_front method (which adds an element to the top of the list) for it? And can I do it somehow?
Thanks in advance.


#2

Here’s a recursive solution. Probably not the best one. I’ve added some explanation in the comments, and you can test it in the playground here: http://play.rust-lang.org/?gist=beb70262e13c3a1dc18588eae6dd2542&version=stable&mode=debug

#[derive(Debug)]        // This will let you debug-print the list
pub enum List<T> {      // You need <T> for List to be generic
    EmptyNode,
    Node { element: T, next: Box<List<T>> }
}

// Implement some methods for List<T>
//   where T is any type
impl<T> List<T> {
    pub fn push_front(&mut self, item: T) {
        match self {
        
            // If the current node is empty, change it to contain an element
            List::EmptyNode => {
                *self = List::Node { element: item, next: Box::new(List::EmptyNode) };
            }
            
            // If the current node is not empty, call push_front on the next node
            List::Node { next, .. } => next.push_front(item),
        }
    }
}

#3

Thank you. While trying i didn’t even think of recursive solution to this problem. Probably i should use recursion in rust much more often then in C++ ))


#4

By push_front I assume you meant adding to the front of the list. @mistodon’s solution adds to the back, and just keeps pushing the empty data to the tail. You should read http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html as it gives thorough coverage on this frequent learning exercise. But here’s a naive impl (covered in that book as well):

struct List<T> {
    head: Node<T>,
}

enum Node<T> {
    Empty,
    Data { element: T, next: Box<Node<T>> },
}

impl<T> List<T> {
    fn push_front(&mut self, val: T) {
        let new_head = Node::Data {
            element: val,
            next: Box::new(std::mem::replace(&mut self.head, Node::Empty)),
        };
        self.head = new_head;
    }
}

#5

Ah, my bad - got it backwards. And to be honest, I used recursion just because it was easy, not because it’s particularly good-in-rust or anything like that.

I also recommend the above book - or if it’s not too daunting, you could probably learn a lot from the standard library’s implementation: https://github.com/rust-lang/rust/blob/master/src/liballoc/linked_list.rs


#6

Funny I did the exact same thing when I went through the Box section of the 2nd ed Rust book. I was surprised that the simple “Cons” enum the book uses as an example is as tricky to work with as it is. I was also surprised that it required the use of mem::replace which the book hadn’t mentioned yet and as far as I can tell, requires redundant copies to satisfy the compilers desire for references to be valid at all times.

enum List {
    Link(i32, Box<List>),
    Nil,
}

Here’s the push_back/front (aka append/prepend) functions I came up with:

    fn push_back(&mut self, val : i32) {
        use std::mem;

        match self {
            List::Link(v, next) => {
                // We need to create a boxed version of self so that self.next can point to it
                // This is tricky because of our use of references. We can't move the current
                // "next" out of self and into our new version without replacing it with
                // something valid, so we put a List::Nil in it's place.
                let old_next = mem::replace(next, Box::new(List::Nil));
                let old_self = List::Link(*v, old_next);

                // Update self to have the new val and point to the old list as "next"
                mem::replace(next, Box::new(old_self));
                *v = val;
            },
            List::Nil => {
                *self = List::Link(val, Box::new(List::Nil));
            }
        }
    }

To make the push_back work required switching to nightly and enabling NLL:

    fn push_back(&mut self, val : i32) {
        let mut x = self;
        while let List::Link(_, next) = x {
            x = next;
        }
        *x = List::Link(val, Box::new(List::Nil));
    }

As a note, a nice extension to Rust’s unsafe functionality would be to let you fiddle with references so as not to require mem::replace(). IMHO, the following is much cleaner and simple to understand than the original.

    fn push_front_with_unsafe(&mut self, val : i32) {
        match self {
            List::Link(v, next) => {
                unsafe references { // not a real rust feature
                    next = Box::new(List::Link(*v, next));
                }
                *v = val;
            },
            List::Nil => {
                *self = List::Link(val, Box::new(List::Nil));
            }
        }
    }

It turns out there’s a cleaner, but still clunky IMHO, way to address the problem we needed mem::replace() for above. I got this from a postponed RFC https://github.com/ticki/rfcs/blob/replace_with/text/0000-mem-replace-with.md

pub fn replace_with<T, F>(mut_ref: &mut T, fn_replace: F)
    where F: FnOnce(T) -> T {
    use std::ptr;
    unsafe {
        let old_t = ptr::read(mut_ref);
        let new_t = fn_replace(old_t);
        ptr::write(mut_ref, new_t);
    }
}

    fn push_front2(&mut self, val : i32) {
        match self {
            List::Link(v, next) => {
                replace_with(next, |orig_next| Box::new(List::Link(*v, orig_next)));
                *v = val;
            },
            List::Nil => {
                *self = List::Link(val, Box::new(List::Nil));
            }
        }
    }

#7

Yep, that’s even more interesting for me. Your solution actually adds one more layer of abstraction. As i understand without a wrapping struct List i can’t modify the head. Thank you/ Btw, also thank you for the mem::replace function. Didn’t know about it.


#8

@steveklabnik I’ve enjoyed working through the Rust Prog Book but have you considered taking the Cons list example in the Box section and working through push_back/push_front (aka append/prepend) routines as examples? Us old C hacks can’t help but try to build a little linked list implementation as we go. (I did discover a how to create linked lists with Rust webpage out there.) It’s the self-referential Cons enum aspect whose consequences are not at all obvious and it’s pretty tricky for a beginner to figure out the append/prepend routines for themselves. I spent several hours trying to work around the borrow checker rules for what would have taken seconds in C. The need for mem::replace definitely came as a surprise and discovering the “replace_with” type helper technique made a big difference to my confidence that I wouldn’t be forced to stand on my head to code in Rust.

Honestly, IMHO, replace_with seems like a critical missing built-in feature currently. Arguably, something cleaner than replace_with would be more ideal but it’s still pretty good.


#9

Maybe! We already have “learning rust with too many linked lists” and the book is already quite long… it’s hard to balance all of the things.


#10

@steveklabnik on second thought, simply referring out to “Too many linked lists” and mentioning that writing operations to manipulate the self-referential Cons enum list is much harder than it looks would have solved my problem.

IMHO, that is the kind of information that C programmers will want to see in order to gain comfort with Rust. I’ve encountered a lot of C code over the years, especially drivers, OS and deeply embedded code, where regular structs have been chained together in some way via pointers embedded right inside them.