How do you remove the last node from a singly linked list?

help
7

Ok, I have looked into this, and here is code equivalent to @EFanZh's last suggestion (with unfallible .unwrap()s):

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

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

fn remove_last_node_iterative<T> (
    mut list: &'_ mut List<T>,
)
{
    if list.is_none() { return; }
    // invariant: list = &mut Some(ref mut node);
    //        <=> list.as_mut() = Some(node);
    loop {
        let node = list.as_mut().unwrap(); // thanks to the invariant
        if node.tail.is_some() { // next-iteration invariant?
            #[cfg(not(feature = "polonius"))]
            let node = list.as_mut().unwrap(); // thanks to the invariant
            list = &mut node.tail;
        } else {
            *list = None;
            return;
        }
    }
}

As you can see, there is kind of a "dumb" redefinition of node needed until we get the next version of the borrow checker, polonius, that would allow us not to need such "hack".

That is, the compilation with polonius

  • cargo +nightly rustc --features polonius -- -Zpolonius

works fine.

2 Likes