LinkedList push_front method

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.

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: Rust Playground

#[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),
        }
    }
}
1 Like

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

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 Learning Rust With Entirely Too Many Linked Lists 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;
    }
}
3 Likes

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

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));
            }
        }
    }
1 Like

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.

@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.

1 Like

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.

@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.

2 Likes