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

[EFanZh]

I want to write a function that removes the last node from a singly linked list with as little overhead as possible using only safe Rust codes. How good can you do?

Here is the definition of my singly linked list, there is nothing special about it:

struct Node<T> {
    value: T,
    next: Option<Box<Self>>,
}

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

For reference, here is a recursive version that works correctly on not very long lists:

fn remove_last_node_recursive<T>(node_ref: &mut List<T>) {
    let next_ref = &mut node_ref.as_mut().unwrap().next;

    if next_ref.is_some() {
        remove_last_node_recursive(next_ref);
    } else {
        *node_ref = None;
    }
}

But this version has two problems:

1. Although the recursive call is a tail call (correct me if I’m wrong), tail call optimization isn’t guaranteed on Rust, so for a very long list, stack overflow could happen.
2. The recursive call is called with a Some variant, but the called function still checks the variant type with a unwrap call.

---

For problem 1, I tried to convert it into a iterative version since all recursive calls are tail calls, but failed. This is what I have tried:

fn remove_last_node_iterative<T>(mut node_ref: &mut List<T>) {
    loop {
        let next_ref = &mut node_ref.as_mut().unwrap().next;

        if next_ref.is_some() {
            node_ref = next_ref;
        } else {
            break;
        }
    }

    *node_ref = None; // This line causes lifetime error.
}

The code above does not work due to lifetime error. I’m not sure why. Is it expected that some tail recursive functions can’t be converted into a iterative one? Or is it a bug in Rust? I know that Drop could cause some fake tail calls but I don’t think this is the case.

I have asked this problem on Stack Overflow, but didn’t get a satisfying answer.

The following implementation is from Stack Overflow:

fn remove_last_node_iterative<T>(mut node_ref: &mut Option<Box<Node<T>>>) {
    while node_ref.as_ref().unwrap().next.is_some() {
        node_ref = &mut node_ref.as_mut().unwrap().next;
    }
    *node_ref = None;
}

I think this one has too many unwrap calls.

---

For problem 2, I have tried to write a infinitely nested code to get some insight. Of course you can’t really write a infinitely nested code, so my code can only work for lists with up to 5 nodes. Here is my code:

fn remove_last_node_unrolled<T>(first_node_ref: &mut List<T>) {
    if let Some(first_node) = first_node_ref {
        let second_node_ref = &mut first_node.next;

        if let Some(second_node) = second_node_ref {
            let third_node_ref = &mut second_node.next;

            if let Some(third_node) = third_node_ref {
                let fourth_node_ref = &mut third_node.next;

                if let Some(fourth_node) = fourth_node_ref {
                    let fifth_node_ref = &mut fourth_node.next;

                    if let Some(fifth_node) = fifth_node_ref {
                        let sixth_node_ref = &mut fifth_node.next;

                        if let Some(sixth_node) = sixth_node_ref {
                            unimplemented!();
                        } else {
                            *fifth_node_ref = None;
                        }
                    } else {
                        *fourth_node_ref = None;
                    }
                } else {
                    *third_node_ref = None;
                }
            } else {
                *second_node_ref = None;
            }
        } else {
            *first_node_ref = None;
        }
    } else {
        unreachable!();
    }
}

You get the idea. I also can’t convert this one into a loop because I discovered that I need to access a mutable reference to a Option<Box<Node<T>>> and a mutable reference to Node<T> that Option<Box<Node<T>>> owns at the same time so it doesn’t work.

---

So how would you write the function?

[DevinR528]

Here is a playground to help test out ideas. I'll see what I can do, if anything .

[alice]

The reason this is tricky is that you can't have several mutable references to the same thing, but the non-unwrap ways of doing this involve having a mutable reference to both the option and the node inside that option. So to avoid the issues, they just have a reference to the option, but then you need an unwrap to access the inner item, even if you know it's not None.

[RustyYato]

Here's what I can up with

pub fn remove_last_node_iterative<T>(mut node_ref: &mut Option<Box<Node<T>>>) {
    while let Some(node_ref_inner) = node_ref.take() {
        if node_ref_inner.next.is_some() {
            let node_ref_inner = node_ref.get_or_insert(node_ref_inner);
            node_ref = &mut node_ref_inner.next;
        } else {
            *node_ref = None;
        }
    }
}

[DevinR528]

Here's a recursive version with no unwraps

fn remove_last_node_recursive<T>(node_ref: &mut List<T>) -> List<T> {
    if let Some(next_ref) = &mut node_ref.as_mut() {
        if next_ref.next.is_some() {
            remove_last_node_recursive(&mut next_ref.next)
        } else {
            node_ref.take()
        }
    } else {
        None
    }
}

it also returns the removed node, I do like @RustyYato less nesting having all the if else's in mine is unfortunate

[EFanZh]

@RustyYato I don’t think take the node out then insert it back is a good idea.

@DevinR528 Both if let and unwrap will check the variant type of the Option, so your code have the same number of variant type checks as my recursive ones.

It seems that for now, the best solution for me is the one from Stack Overflow:

fn remove_last_node_iterative<T>(mut node_ref: &mut Option<Box<Node<T>>>) {
    while node_ref.as_ref().unwrap().next.is_some() {
        node_ref = &mut node_ref.as_mut().unwrap().next;
    }

    *node_ref = None;
}

Although the code above has two unwraps, maybe the compiler can spot the similarity and optimize one unwrap away.

I have submitted an issue on GitHub: Cannot convert this tail recursive function into an iterative one due to lifetime error · Issue #63908 · rust-lang/rust · GitHub for this. I hope my iterative function will code compile come day.

[Yandros]

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.

[EFanZh]

You are right. I didn’t know that there are a new version of the borrow checker. My iterative code indeed compiles with the new polonius borrow checker. It seems that I just need to wait patiently until the new borrow checker is stablized.