Get mutable reference to the nth node in a List

help
1

I have defined a List type which is recommended by many articles.
Is the "nth_mut" method below the idiomatic way to get the mutable reference to the nth node? The method works but seems complicated and not efficient?

UPDATE: I mean the type definition is recommended not the nth_mut() method.

type Link = Option<Box<Node>>;

struct List {
  head: Link
}

struct Node {
  value: i32,
  next: Link
}

fn nth_mut(link: &mut Link, n: i32) -> &mut Link {
  let mut iter = link.as_mut().map(|node| &mut **node);

  for _ in 0..n-1 {
    iter.take().map(|node| {
      iter = node.next.as_mut().map(|node| &mut **node);
    });
  }

  &mut iter.unwrap().next
}
2

Is it really recommended? Or just used as a common first example?

I'd think the better recommendation is to just use LinkedList, and then list.iter_mut().nth(n) should get what you want.

1 Like
3

Thanks for the quick reply. Yes I know LinkedList. I think list.iter_mut() is mentioned here Splitting Borrows and the nth_mut() method is roughly a copy of the code in the link. Just wonder whether nth_mut() is efficient?

4

It's probably fine for efficiency, as the compiler can see enough here to optimize nicely, so I'd focus on correctness and readability. There are two problems I see:

  1. n-1 will underflow if n == 0 -- except you're using i32. But that itself is non-idiomatic, as lengths and indexes are almost always usize in Rust. (u64 lengths if dealing with files.) What does it mean if someone asks for a negative n?
  2. the unwrap is a sign that you're not handling a case -- what if the list isn't long enough? It should probably return Option, and I would lean toward returning the node, Option<&mut Node>, if not the value itself.

So I would write your function something like this:

impl List {
    pub fn nth_mut(&mut self, n: usize) -> Option<&mut Node> {
        let mut link = self.head.as_mut();
        for _ in 0..n {
            link = match link {
                Some(node) => node.next.as_mut(),
                None => return None,
            }
        }
        link.map(|n| &mut **n)
    }
}

But it's more idiomatic to just implement an iter_mut and use Iterator::nth. You get a lot of nicely-composable functionality once you implement iterators.

5

Thanks @cuviper. You're right, your code is more robust.

What I want to do is like this, say I have a list of 6 elements:
1->2->3->4->5->6
I want to transform it to 1->4->2->5->3->6.

Your solution is ok, and the code is more intuitive. I can get Option<&mut Node> and exchange the "value" in Node. But if the "value" is large, I think it's better to get &mut Option and just exchange the Option.

So nth_mut() returns &mut Option and the code is much more non-intuitive and complicated. Actually I can't work out how to write nth_mut() until I read Splitting Borrows...