Delete a node in singly linked list in Rust

Question

I am new to Rust and want to write linked list in Rust to have fun. I am confused about how to delete a node in the linked list. Here is my simple code.

#[derive(Debug)]
struct Node{
    v: usize,
    next: Option<Box<Node>>,
}

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn remove(&mut self, v: usize) -> Option<usize> {
        let mut current_node: &mut Option<Box<Node>> = &mut self.head;
        loop {
           match current_node {
                None => break,
                Some(node) => {
                    if node.v == v {
                        // current_node = what? 
                        // ???????????????
                        break;
                    } else {
                        current_node = &mut node.next;
                    }
                },
            };
        }

        match current_node.take().map(|x| *x) {
            Some(node) => {
                *current_node = node.next;
                return Some(node.v)
            },
            None => None,
        }
    }
}

And here is the rust playground. I am using the nightly version and edition = 2018. In the loop, I try to find the node whose next node contains the value that I search for. However, I am confused about what to write in the ?? position.

Not an exact duplicate but highly (!!!) related! https://stackoverflow.com/questions/41653148/singly-linked-list-in-rust — hellow, Nov 30 '18 at 09:54
Btw, you cannot modify `current_node` in that context, because it is currently borrowed, so this approach won't work. — hellow, Nov 30 '18 at 09:56
@hellow Thanks. I realized this problem and read the link you attached. However I still do not know how to fix it 0.0 — YjyJeff, Nov 30 '18 at 10:06
I hope you also read the provided link in the answer http://cglab.ca/~abeinges/blah/too-many-lists/book/third.html This it **the** ultimate reference for linked lists in rust. — hellow, Nov 30 '18 at 10:20

Peter Hall · Accepted Answer · 2018-11-30T12:58:09.087

There isn't really code that can go in that space to fix it; you'll need to make some bigger changes.

One of the problems is that you have mutably borrowed the current node in current_node, but then need to mutate it while that reference still exists.

Making use of non-lexical lifetimes in Edition 2018, you can do:

impl LinkedList {
    fn remove(&mut self, v: usize) -> Option<usize> {
        let mut current = &mut self.head;
        loop {
            match current {
                None => return None,
                Some(node) if node.v == v => {
                    *current = node.next.take();
                    return Some(v);
                },
                Some(node) => {
                    current = &mut node.next;
                }
            }
        }
    }
}

Somehow, using the match guard if node.v == v to make two match arms, instead of using an if condition inside one match arm, lets the borrower checker deduce that this is safe. I'm not sure why the if statement inside the match arm isn't allowed - there are some of the opinion that this could be a bug.

score 0 · Answer 2 · answered Jan 15 '21 at 02:38

inspire by above answer, my solution is:

fn removeKFromList(mut head: ListNode<i32>, k: i32) -> ListNode<i32> {
  if head.is_none() {
        return None;
  }

  let mut current = &mut head;
  loop {
      match current {
          None => break,
          Some(node) if node.value == k => {
              *current = node.next.take();
          },
          Some(node) => {
              current = &mut node.next;
          }
      }
  }
  return head;
}

score 0 · Answer 3 · answered Jan 10 '22 at 23:37

Here is solution, if you have generic List, which accepts arbitrary type of content type T and returns deleted content to caller:

impl<T> LinkedList<T> {
    pub fn remove_f<F: Fn(&T) -> bool>(&mut self, comparator: F) -> Option<T> {
        let mut curr_link = &mut self.head;
        loop {
            match curr_link {
                None => return None,
                Some(node_ref) if comparator(&node_ref.elem) => {
                    let node = curr_link.take().unwrap();
                    *curr_link = node.next;
                    return Some(node.elem);
                },
                Some(node) => curr_link = &mut node.next,
            };
        }
    }
}

Use example, assume T = &str and list contains element with value "1" and no element with value "smth":

assert_eq!(list.remove_f(|node| "1".eq(node.deref())), Some("1"));
assert_eq!(list.remove_f(|node| "smth".eq(node.deref())), None);

Delete a node in singly linked list in Rust

3 Answers3

Linked