Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Delete a node in singly linked list in Rust

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.

like image 812
YjyJeff Avatar asked Nov 30 '18 09:11

YjyJeff


People also ask

How do I remove a specific item from a linked list?

Type 1: remove() Method It is used to remove an element from a linked list. The element is removed from the beginning or head of the linked list. Parameters: This function does not take any parameter. Return Value: This method returns the head of the list or the element present at the head of the list.

How do you delete a node from the end of a linked list?

Approach: To delete the last node of a linked list, find the second last node and make the next pointer of that node null. Algorithm: If the first node is null or there is only one node, then they return null. Create an extra space secondLast, and traverse the linked list till the second last node.

How do you remove a node?

To delete a node from linked list, we need to do following steps. 1) Find previous node of the node to be deleted. 2) Change the next of previous node. 3) Free memory for the node to be deleted.


1 Answers

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.

like image 156
Peter Hall Avatar answered Sep 29 '22 17:09

Peter Hall