pointersrustlinked-list

how to modify a linked list by using pointers only


I have a linked list of Option<Box<ListNode>> type, a node of this list contains two properties: value (i32) and next (Option<Box<ListNode>>). I've created a vector of pointers (Vec<&Box<ListNode>>) with the purpose of serving to modify the original list as showed in the following picture:

enter image description here

Note: the resulting list should be: L: 1 -> 2 -> n-1 -> n

This is my code, it needs some fixes but at the moment I need to know if I can modify my linked list by using pointers.

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    head.as_ref()?;

    type NodeRef<'a> = &'a Box<ListNode>;
    type OptNodeRef<'a> = Option<NodeRef<'a>>;

    const MAX_NODES: u16 = 300;
    // let mut head = head;
    let mut current: OptNodeRef = head.as_ref();
    let mut node_ref: OptNodeRef = None;
    let mut vec_ref: Vec<NodeRef> = Vec::with_capacity(MAX_NODES as usize);
    let mut counter: u16 = 0;

    while let Some(node) = current {
        if node_ref.is_none() || node_ref.unwrap().val != node.val {
            node_ref = Some(node);
            if counter > 0 { 
                vec_ref.push(node);
            }
            counter = 0;
        } else {
            counter += 1;
        }

        current = node.next.as_ref();
    }
    
    if counter > 0 {
        vec_ref.push(node_ref.unwrap());
    }
    // vec_ref.into_iter().map(|t| t.val).for_each(|e| println!("{:?}", e));

    // my problem starts from here...
    for i in 0..vec_ref.len() - 1 {
        vec_ref[i].next = Some(*vec_ref[i + 1]);
    }

    if let Some(last_node) = vec_ref.last() {
        last_node.next = None;
    }

    if let Some(first_node) = vec_ref.first() {
        Some(**first_node)
    } else {
        None
    }
}

how to get it? I've tried some things but I always get an error related to borrow, move, mismatch errors. It seems simple to modify "next" property but I'm out of ideas.


Solution

  • Here is my thought, first, basically avoid using linked list in Rust, rust is just not a good language for using linked list because the ownershipe model.

    second, if you want a link list I think you should tried to avoid messing with reference too much. Pointer is already hard to think about, let alone pointer comply with ownership rule.

    think about who own the piece of data.

    #[derive(PartialEq, Eq, Clone, Debug)]
    pub struct ListNode {
        pub val: i32,
        pub next: Option<Box<ListNode>>,
    }
    
    impl ListNode {
        #[inline]
        pub fn new(val: i32) -> Self {
            ListNode { next: None, val }
        }
    
        /// Functions I added for testing
        /// 
        /// Push an element to the end of the list
        pub fn push(&mut self, val: i32) {
            let mut current: &mut ListNode = self;
            while current.next.is_some() {
                current = current.next.as_mut().unwrap();
            }
            current.next = Some(Box::new(ListNode { val, next: None }));
        }
        /// Print Out the list
        pub fn print(&self) {
            print!("[{:>3?}]", self.val);
            let mut current: &ListNode = self;
            while current.next.is_some() {
                current = current.next.as_ref().unwrap();
                print!(" -> [{:>3?}]", current.val);
            }
    
            println!("");
        }
    }
    
    /// I refactored the whole function
    pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // The head of the list, if there aren't a list, return None
        let mut head: Box<ListNode> = head?;
        let mut current: Option<Box<ListNode>> = head.next.take();
        let mut tail: &mut Box<ListNode> = &mut head;
    
        // we TAKE the second element as the current node
        //
        // you can think of it as
        //
        //               |- tail
        //               v
        // head : () -> [first val]
        //
        // current: () -> [second val] -> [thrid val] -> ...
        //
    
        // Then we keep dequeuing the current
        // when current is None, we know the list ended
        while let Some(mut c) = current {
            //
            //                                     | tail
            //                                     v
            //  head : () -> [1] -> [2] -> ... -> [4]
            //  c    : () -> [5] -> [6]-> ...
            //
            // TAKE out the next node as the next current
            current = c.next.take();
            //
            //                                        | tail
            //                                        v
            //  head    : () -> [1] -> [2] -> ... -> [4]
            //  c       : () -> [5]
            //  current : () -> [6] -> [7]-> ...
            //
            // if the c.val is not equal to the last list, we push it to the end of the list
            if c.val != tail.val {
                tail.next = Some(c);
                tail = tail.next.as_mut().unwrap();
                //
                //                                               | tail
                //                                               v
                //  head    : () -> [1] -> [2] -> ... -> [4] -> [5]
            }
        }
    
        Some(head)
    }
    fn main() {
        let mut list: ListNode = ListNode::new(1);
        list.push(2);
        list.push(2);
        list.push(3);
        list.push(4);
        list.print();
        let new_list: Box<ListNode> = delete_duplicates(Some(Box::new(list))).unwrap();
        new_list.print();
    }
    

    output

    [  1] -> [  2] -> [  2] -> [  3] -> [  4]
    [  1] -> [  2] -> [  3] -> [  4]
    

    that way, head own the whole list, and tail handle the mutation of the list. which comply with the ownership rule, one owner, and only one mutable reference.

    Performance

    performance is way faster if the function take reference instead of the the whole list like Andrea Corbellini's solution

    use std::io::Write;
    
    #[derive(PartialEq, Eq, Clone, Debug)]
    pub struct ListNode {
        pub val: i32,
        pub next: Option<Box<ListNode>>,
    }
    
    impl ListNode {
        #[inline]
        pub fn new(val: i32) -> Self {
            ListNode { next: None, val }
        }
    
        /// Functions I added for testing
        ///
        /// Push an element to the end of the list
        pub fn push(&mut self, val: i32) {
            let mut current: &mut ListNode = self;
            while current.next.is_some() {
                current = current.next.as_mut().unwrap();
            }
            current.next = Some(Box::new(ListNode { val, next: None }));
        }
        /// Print Out the list
        pub fn print(&self) {
            print!("[{:>3?}]", self.val);
            let mut current: &ListNode = self;
            while current.next.is_some() {
                current = current.next.as_ref().unwrap();
                print!(" -> [{:>3?}]", current.val);
            }
    
            println!("");
        }
    }
    
    /// I refactored the whole function
    pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // The head of the list, if there aren't a list, return None
        let mut head: Box<ListNode> = head?;
        let mut current: Option<Box<ListNode>> = head.next.take();
        let mut tail: &mut Box<ListNode> = &mut head;
    
        // we TAKE the second element as the current node
        //
        // you can think of it as
        //
        //               |- tail
        //               v
        // head : () -> [first val]
        //
        // current: () -> [second val] -> [thrid val] -> ...
        //
    
        // Then we keep dequeuing the current
        // when current is None, we know the list ended
        while let Some(mut c) = current {
            //
            //                                     | tail
            //                                     v
            //  head : () -> [1] -> [2] -> ... -> [4]
            //  c    : () -> [5] -> [6]-> ...
            //
            // TAKE out the next node as the next current
            current = c.next.take();
            //
            //                                        | tail
            //                                        v
            //  head    : () -> [1] -> [2] -> ... -> [4]
            //  c       : () -> [5]
            //  current : () -> [6] -> [7]-> ...
            //
            // if the c.val is not equal to the last list, we push it to the end of the list
            if c.val != tail.val {
                tail.next = Some(c);
                tail = tail.next.as_mut().unwrap();
                //
                //                                               | tail
                //                                               v
                //  head    : () -> [1] -> [2] -> ... -> [4] -> [5]
            }
        }
    
        Some(head)
    }
    
    pub fn delete_duplicates_2(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // take ownership of the head, and we will manipulate this directly.
        let mut current = head;
        // Mutable reference to 'current' node. We use 'as_mut' and 'and_then' to traverse and modify the list in place
        let mut current_ref = current.as_mut();
    
        while let Some(curr_node) = current_ref {
            // check if the next node is a duplicate
            while curr_node
                .next
                .as_ref()
                .map_or(false, |next_node| next_node.val == curr_node.val)
            {
                //skip the duplicate
                curr_node.next = curr_node.next.as_mut().unwrap().next.take();
            }
            // Move to the next node
            current_ref = curr_node.next.as_mut();
        }
        current
    }
    
    pub fn delete_duplicates_3(head: &mut Option<Box<ListNode>>) {
        // Make sure that `node` is `Option<&mut Box<ListNode>>`, to
        // avoid taking ownership of nodes after the head (which would
        // not be allowed by Rust)
        let mut node = head.as_mut();
    
        while let Some(this) = node {
            // Loop through every node that shares the same value as `this`
            loop {
                if let Some(ref mut next) = this.next {
                    if this.val == next.val {
                        // `this` and `next` have the same value.
                        // Connect `this` to `next.next`, so that the
                        // list changes from:
                        //
                        //   ... -> this -> next -> next.next -> ...
                        //
                        // to:
                        //
                        //   ... -> this -> next.next -> ...
                        //
                        // The use of `take()` ensures that `next.next`
                        // is replaced with `None` (this avoids taking
                        // multiple ownerships).
                        this.next = next.next.take();
                        continue;
                    }
                }
                // Either there's no next node, or the next node has a
                // different value than `this`
                break;
            }
            node = this.next.as_mut();
        }
    }
    
    fn delete_duplicates_4(head: &mut Option<Box<ListNode>>) {
        if head.is_none() {
            return;
        }
        let mut head = head.as_mut().unwrap();
    
        while let Some(ref n) = head.next {
            if head.val == n.val {
                head.next = head.next.take().unwrap().next;
            } else {
                head = head.next.as_mut().unwrap();
            }
        }
    }
    
    fn make_list(len: usize) -> ListNode {
        let mut a = 1;
        let mut b = 1;
        let mut list = ListNode::new(a);
    
        for _ in 0..len {
            let t = b;
            b = (a + b) % 10;
            a = t;
            list.push(a);
        }
    
        list
    }
    
    fn bench(len: usize) {
        let list = make_list(len);
    
        let N = 2048;
    
        println!("Bench Testing n = {}", len);
        {
            print!("    running delete_duplicates   . . . ");
            std::io::stdout().flush().unwrap();
            let mut dt = 0;
            for _ in 0..N {
                let list = Some(Box::new(list.clone()));
                let t0 = std::time::Instant::now();
                let _ = delete_duplicates(list).unwrap();
                dt += t0.elapsed().as_micros();
            }
            println!("{:>8}us", (dt as f64) / (N as f64));
        }
        {
            print!("    running delete_duplicates_2 . . . ");
            std::io::stdout().flush().unwrap();
            let mut dt = 0;
            for _ in 0..N {
                let list = Some(Box::new(list.clone()));
                let t0 = std::time::Instant::now();
                let _ = delete_duplicates_2(list).unwrap();
                dt += t0.elapsed().as_micros();
            }
            println!("{:>8}us", (dt as f64) / (N as f64));
        }
        {
            print!("    running delete_duplicates_3 . . . ");
            std::io::stdout().flush().unwrap();
            let mut dt = 0;
            for _ in 0..N {
                let mut list = Some(Box::new(list.clone()));
                let t0 = std::time::Instant::now();
                let _ = delete_duplicates_3(&mut list);
                dt += t0.elapsed().as_micros();
            }
            println!("{:>8}us", (dt as f64) / (N as f64));
        }
        {
            print!("    running delete_duplicates_3 . . . ");
            std::io::stdout().flush().unwrap();
            let mut dt = 0;
            for _ in 0..N {
                let mut list = Some(Box::new(list.clone()));
                let t0 = std::time::Instant::now();
                let _ = delete_duplicates_4(&mut list);
                dt += t0.elapsed().as_micros();
            }
            println!("{:>8}us", (dt as f64) / (N as f64));
        }
    }
    
    fn main() {
        for i in 5..=11 {
            bench(1 << i);
        }
    }
    

    Output

    Bench Testing n = 32
        running delete_duplicates   . . . 2.052734375us
        running delete_duplicates_2 . . . 2.16943359375us
        running delete_duplicates_3 . . . 0.0556640625us 
        running delete_duplicates_4 . . . 0.1826171875us
    Bench Testing n = 64
        running delete_duplicates   . . . 4.1171875us
        running delete_duplicates_2 . . . 5.03515625us
        running delete_duplicates_3 . . . 0.33154296875us
        running delete_duplicates_4 . . . 0.06396484375us
    Bench Testing n = 128
        running delete_duplicates   . . . 8.5419921875us
        running delete_duplicates_2 . . . 8.87158203125us
        running delete_duplicates_3 . . . 1.1669921875us
        running delete_duplicates_4 . . . 1.193359375us
    Bench Testing n = 256
        running delete_duplicates   . . . 18.2841796875us
        running delete_duplicates_2 . . . 20.169921875us
        running delete_duplicates_3 . . . 2.74169921875us
        running delete_duplicates_4 . . . 2.35791015625us
    Bench Testing n = 512
        running delete_duplicates   . . . 37.2880859375us
        running delete_duplicates_2 . . . 36.0595703125us
        running delete_duplicates_3 . . . 5.30224609375us
        running delete_duplicates_4 . . . 5.31103515625us
    Bench Testing n = 1024
        running delete_duplicates   . . . 66.796875us
        running delete_duplicates_2 . . . 69.91552734375us
        running delete_duplicates_3 . . . 9.84814453125us
        running delete_duplicates_4 . . . 10.646484375us
    Bench Testing n = 2048
        running delete_duplicates   . . . 133.638671875us
        running delete_duplicates_2 . . . 143.2666015625us
        running delete_duplicates_3 . . . 20.03955078125us
        running delete_duplicates_4 . . . 20.87939453125us