4

This is the data structure I am using to represent a single linked list:

type Link = Option<Box<Node>>;

pub struct Node {
    elem: i32,
    next: Link,
}

I would like to implement a method to remove the Nth node from the end of the list:

// Original list
A -> B -> C -> D -> None

// remove 1 from the end of the original list
A -> B -> C -> None

// Remove 2 from the end of the original list
A -> B -> D -> None

I am fighting with the borrow checker all the time:

fn remove_nth_node_from_end(list: &mut Link, n: usize) {
    if list.is_none() {
        return;
    }
    let mut i = 0;
    let mut fast = list;
    while let Some(ref mut node) = {fast} {
        if i == n {
            break;
        }
        i += 1;
        fast = &mut node.next;
    }

    // issues start here, since I need to mutably borrow
    // the list (and it has already been moved above for fast)
    // but without moving I have troubles implementing the above loop
    let mut slow = &mut list;
    // iterate over the list using slow and fast
    // when fast is None
    //   slow.next = slow.next.next
}

error[E0596]: cannot borrow immutable argument `list` as mutable
  --> src/lib.rs:25:25
   |
25 |     let mut slow = &mut list;
   |                         ^^^^ cannot borrow mutably
help: consider removing the `&mut`, as it is an immutable binding to a mutable reference
   |
25 |     let mut slow = list;
   |                    ^^^^

error[E0382]: use of moved value: `list`
  --> src/lib.rs:25:25
   |
13 |     let mut fast = list;
   |         -------- value moved here
...
25 |     let mut slow = &mut list;
   |                         ^^^^ value used here after move
   |
   = note: move occurs because `list` has type `&mut std::option::Option<std::boxed::Box<Node>>`, which does not implement the `Copy` trait

How can I implement the remaining part of the method?

Please note my methods does not take self as argument and the list argument needs to be moved twice at least with the current implementation.

Nick
  • 10,309
  • 21
  • 97
  • 201
  • I believe your question is answered by the answers of [Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time](https://stackoverflow.com/q/37986640/155423). If you disagree, please [edit] your question to explain the differences. Otherwise, we can mark this question as already answered. – Shepmaster Nov 10 '18 at 18:29
  • See also the [26 previous questions that are linked to the suggested duplicate](https://stackoverflow.com/questions/linked/37986640?lq=1) – Shepmaster Nov 10 '18 at 18:31
  • Especially [Deleting a node from singly linked list has the error “cannot move out of borrowed content”](https://stackoverflow.com/q/51134192/155423) – Shepmaster Nov 10 '18 at 18:32
  • @Shepmaster The first link you provided does what I do with the fast "pointer", but my problem arises when I need to follow also the slow pointer, because the anchor/head has been moved already. – Nick Nov 10 '18 at 18:34
  • See this quote from [the last question I linked](https://stackoverflow.com/q/51134192/155423): *If your code were able to compile, you'd have a mutable reference to `previous` as well as a mutable reference to `current`. However, you can get a mutable reference to `current` from `previous`. This would allow you to break Rust's memory safety guarantees!* – Shepmaster Nov 10 '18 at 18:39
  • Possible duplicate of [Deleting a node from singly linked list has the error "cannot move out of borrowed content"](https://stackoverflow.com/questions/51134192/deleting-a-node-from-singly-linked-list-has-the-error-cannot-move-out-of-borrow) – trent Nov 10 '18 at 18:40
  • Here's a (dumb) way to make the borrow checker happy by using recursion: https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=b63cbd2560c18a0477a03a3c87013845 – trent Nov 10 '18 at 19:30
  • @trentcl thanks for the example, can you explain how this line works exactly? `*list = list.as_mut().unwrap().next.take();` – Nick Nov 10 '18 at 23:17
  • I used `.take()` to get the value of the `.next` field, replacing it with `None`. Effectively, I first divide the list into a head and a tail, and then replace the head with the tail. The head doesn't retain any references to the tail nor vice versa, so the borrow checker is fine with this. – trent Nov 10 '18 at 23:56
  • 1
    On reflection, I think I would instead write that as `*list = list.take().and_then(|l| l.next);`. You should familiarize yourself with [`Option`](https://doc.rust-lang.org/std/option/enum.Option.html)'s methods; there is often a conversion that does just what you want. `and_then` returns `None` if `list.take()` is `None`, so this version of `remove_helper` won't panic if you call it with an empty list and `n` of zero. – trent Nov 11 '18 at 00:01

1 Answers1

2

This is how you could write the method without using recursion.

fn remove_nth(list: &mut Link, n: usize) {
    if list.is_none() {
        return;
    }
    let get_length = |l: &Link| {
        let mut length = 0;
        let mut current = l;
        while let Some(n) = {current} {
            length += 1;
            current = &n.next;
        }
        length
    };
    let length = get_length(list);
    let mut i = 0;
    let mut current = list;
    while i < length - n {
        if let Some(link) = {current} {
            current = &mut link.next;
        } else {
            panic!("Invalid node!");
        }
        i += 1;
    }
    *current = current.as_mut().unwrap().next.take();
}

Unfortunately, I didn't manage to make the borrow checker happy by using the more efficient runner pattern.

gliderkite
  • 8,828
  • 6
  • 44
  • 80
  • 1
    @Stargateur of course recursion is less efficient, since space complexity would be O(N) compared to the O(1) of the runner pattern. – gliderkite Nov 11 '18 at 10:18
  • 1
    Every iterative function can be write in the form of tail recursive function, what you are saying is completely false. recursion can do this in O(1) like iterative can do this in O(1). Everything iterative can do recursive can and vice versa. – Stargateur Nov 11 '18 at 11:20
  • 1
    @Stargateur If you were to rewrite this recursively, you'd have to write two recursive algorithms, because it contains two loops. [My recursive solution](https://stackoverflow.com/questions/53242052/how-to-remove-the-nth-node-from-the-end-of-a-linked-list?noredirect=1#comment93370720_53242052) traverses the list only once, but at the cost of O(n) space. So that is the comparison being made here, not recursion vs. iteration in general. – trent Nov 11 '18 at 13:39
  • I think by "runner pattern" gliderkite means the algorithm OP was trying to use, i.e. two pointers that traverse the list `n` nodes apart. When the first pointer reaches the end, the second pointer is pointing at the node to be removed. But to be honest... I don't really see how this solution is more efficient than that. Perhaps I'm missing something. – trent Nov 11 '18 at 13:41
  • 1
    Pheraps I didn't explain myself well. My solution is less efficient than the runner pattern the OP was trying to use, because it needs to iterate in the worst case twice the list (to get its length first), while using the runner pattern you only need to iterate the list once. Nevertheless it's still O(N) time complexity and O(1) space complexity, while the recursive solution is O(N) for both (time and space). – gliderkite Nov 11 '18 at 14:00
  • https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=a916d3d68e8c8520c54acc05c0ed4a80, that simply false here the prove this is the equivalent of your O(1) in space and O(N) in time. – Stargateur Nov 11 '18 at 14:53
  • @gliderkite Yeah, the OP's solution would be more efficient if it worked, because it could advance both pointers in the same loop to save a branch per iteration. But the cost of the branch, unless mispredicted, is probably much less than the cost of following two pointers, so it wouldn't be a huge savings. You could do a comparison using `&` pointers and `RefCell` to find the difference. – trent Nov 11 '18 at 23:37