Recursively pop the last node from a singly linked list

Question

I am exploring different ways of implementing a linked list in Rust as a learning project. In one particular place, I've got some code that works properly, but it makes multiple calls to unwrap--I am under the impression this is generally regarded as unsafe/poor style. I'd like to make it better.

Here are some relevant definitions (I've omitted things not relevant to the question at hand, like push methods). Note that it is a singly linked list, with owning next pointers. Note that for clarity I've separate out the most interesting part into a separate section.

type NodePtr<T> = Option<Box<Node<T>>>;

struct Node<T> {
    data: T,
    next: NodePtr<T>,
}

pub struct LinkedList<T> {
    head: NodePtr<T>,
}

pub struct LinkedListError {
    kind: LinkedListErrorKind,
}

enum LinkedListErrorKind {
    Empty,
}

impl<T> LinkedList<T> {
    pub fn pop_back(&mut self) -> Result<T, LinkedListError> {
        if self.head.is_none() {
            Err(LinkedListError { kind: LinkedListErrorKind::Empty })
        } else {
            Ok(LinkedList::pop_last_node(&mut self.head))
        }
    }
    // definition for pop_last_node goes here...
}

In this particular implementation I'm experimenting with recursive functions, and this is my working version of pop_last_node.

fn pop_last_node(node_ref: &mut NodePtr<T>) -> T {
    match node_ref.as_ref().unwrap().next {
        None => {
            let old_tail = node_ref.take();
            old_tail.unwrap().data
        }
        _ => LinkedList::pop_last_node(&mut node_ref.as_mut().unwrap().next)
    }
}

This is working correctly, but since I'm doing this as a learning experiment, I wanted to see if I could cut down on the unwrap calls and use some more pattern matching. This part of the experiment did not go as well.

Here is my attempt to do so. Unfortunately, this version is much more verbose (and confusing!) than the original. I especially don't like the "fall through out of this scope before you can do anything" part, but I haven't been able to come up with an idea on how to make it better.

fn pop_last_node(node_ref: &mut NodePtr<T>) -> T {
    {
        let next_node = match node_ref.as_mut() {
            None => panic!("Error handling will go here..."),
            Some(node_box) => &mut node_box.next,
        };
        match *next_node {
            None => {
                // fall through to code below
            },
            _ => {
                return LinkedList::pop_last_node(next_node)
            },
        }
    }
    // no sense converting this to a match--the "None" case was already checked above
    node_ref.take().unwrap().data
}

And that's where I am now. The main question is this: Is there a less crazy way to write the pattern matching version? Are there significant ways to improve the clarity or idiomatic-ness of either version?)

Answer 1

Due to the Box, pattern matching with boxes is messy on stable. If you are willing to use nightly until box patterns are stabilized, you can rewrite your pop_back function (instead of just the pop_last_node function):

pub fn pop_back(&mut self) -> Result<T, LinkedListError> {
    fn pop_last_node<T>(node: &mut NodePtr<T>) -> Option<T> {
        match node.take() {
            None => None,
            // is a leaf
            Some(box Node { next: None, data }) => Some(data),
            Some(mut this) => {
                // recurse
                let ret = pop_last_node(&mut this.next);
                // put this subnode back, since it's not a leaf
                *node = Some(this);
                ret
            }
        }
    }
    pop_last_node(&mut self.head).ok_or(LinkedListError {
        kind: LinkedListErrorKind::Empty
    })
}

Try it out in the PlayPen

---

To make the above code work in stable, you can add an inner match instead of the box pattern.

match node.take() {
    None => None,
    Some(n) => match *n {
        // is a leaf
        Node { next: None, data } => Some(data),
        mut this => {
            // recurse
            let ret = pop_last_node(&mut this.next);
            // put the subnode back, since it's not a leaf
            *node = Some(Box::new(this));
            ret
        }
    }
}