patternrustMinor
Recursively pop the last node from a singly linked list
Viewed 0 times
lastthenoderecursivelysinglylistfromlinkedpop
Problem
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
In this particular implementation I'm experimenting with recursive functions, and this is my working version of
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
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 = Option>>;
struct Node {
data: T,
next: NodePtr,
}
pub struct LinkedList {
head: NodePtr,
}
pub struct LinkedListError {
kind: LinkedListErrorKind,
}
enum LinkedListErrorKind {
Empty,
}
impl LinkedList {
pub fn pop_back(&mut self) -> Result {
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 {
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
Solution
Due to the
Try it out in the PlayPen
To make the above code work in stable, you can add an inner
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 {
fn pop_last_node(node: &mut NodePtr) -> Option {
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
}
}
}Code Snippets
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
})
}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
}
}
}Context
StackExchange Code Review Q#94408, answer score: 4
Revisions (0)
No revisions yet.