this is indeed the case, but it's an easy fix.
fundamentally, I don't want to change the type definition in the original code, but that data definition is irregular and has some edge cases which lead to unnecessary complication in the algorithm.
typically, singly linked list is most suitable for insertion and deletion at the head, which can be trivially (and elegantly) implemented, when you have some functional progarmming experience:
// this is a "cons" cell, but I call it "node" here so non-lispers know what it is
// struct Cons<T> { car: T, cdr: List<T> }
struct Node<T> {
value: T,
next: List<T>,
}
// None is Nil, Some is Cons
// enum List<T> { Nil, Cons(Box<Cons<T>>) }
// need a newtype wrapper (or extension trait) if we want to implement methods for it
// the following example snippets ignore this limitation for brevity
type List<T> = Option<Box<Node<T>>>;
impl<T> List<T> {
fn nil() -> Self { None }
fn cons(value: T, next: Self) -> Self {
Some(Box::new(Node { value, next }))
}
}
and push() and pop() is trivial:
impl<T> List<T> {
fn push(&mut self, value: T) {
let next = self.take();
*self = Some(Self::cons(value, next))
}
fn pop(&mut self) -> Option<T> {
let node = self.take()?;
let Node { value, next } = *node;
*self = next;
Some(value)
}
}
with this definitions, even the tail insertion and deletion is very simple. it's still O(n) where n is the length of the list, but we don't need to handle those edge cases like the original code.
here's a recursive version:
impl<T> List<T>
fn push_tail_node(&mut self, node: Box<Node<T>>) {
match self.as_deref_mut() {
Some(curr) => curr.next.push_tail_node(node),
None => *self = List(Some(node)),
}
}
fn pop_tail_node(&mut self) -> Option<Box<Node<T>>> {
match self.as_deref_mut()?.next.pop_tail_node() {
Some(node) => Some(node),
None => self.take(),
}
}
fn push_tail(&mut self, value: T) {
let singleton = Box::new(Node {
value,
next: Self::nil(),
});
self.push_tail_node(singleton);
}
fn pop_tail(&mut self) -> Option<T> {
self.pop_tail_node().map(|node| node.value)
}
}
an iterative implementation is possible, but unfortunately, the snippet below is rejected by the current borrow checker as is, and polonius is required to compile. on stable, you can use unsafe to work around it, but polonius-the-crab is recommended.
impl<T> List<T> {
fn push_tail(&mut self, value: T) {
let singleton = Self::cons(value, Self::nil());
let mut curr: &mut Self = self;
while let Some(curr_node) = curr.as_deref() {
curr = &mut curr_node.next;
}
*curr = singleton;
}
fn pop_tail(&mut self) -> Option<T> {
let mut curr: &mut Self = self;
loop {
let curr_node = curr.as_deref_mut()?;
if curr_node.next.is_some() {
curr = &mut curr_node.next;
} else {
return Some(curr.take().unwrap().value);
}
}
}
}
here's a playground link (with unsafe polonius workaround included):
