rust 链表非递归

待我称王封你为后i 2022-09-04 08:55 200阅读 0赞

简单写了一下rust链表的一些基本操作，`append`，`delete`之类的  
熟悉一下rust之间的借用，和巧用`.take()`方法。

append是用递归的思路，delete使用非递归的。不得不说，非递归的写法很头痛。要考虑到删除头节点和尾节点的情况，所以看起来有点复杂

use std::fmt::Debug;
    
    type List<T> = Option<Box<Node<T>>>;
    
    #[derive(Debug)]
    struct Node<T> { 
        next: List<T>,
        val: T,
    }
    
    impl<T: PartialOrd + Copy + Debug> Node<T> { 
        pub fn new(vals: T) -> Self { 
            Node { 
                next: None,
                val: vals,
            }
        }
        pub fn get_last_mut(&mut self) -> &mut Self { 
            if let Some(ref mut box_node) = self.next { 
                return box_node.get_last_mut();
            } else { 
                return self;
            }
        }
        pub fn append_end(&mut self, val: T) { 
            let node_ = Node::new(val);
            self.get_last_mut().next = Some(Box::new(node_));
        }
        pub fn from(vals: &[T]) -> Node<T> { 
            let mut head = Node::new(vals[0]);
            let length = vals.len();
            for i in 1..length { 
                head.append_end(vals[i])
            }
            head
        }
        pub fn delete(&mut self, idx: i32) -> bool { 
            if idx == 0 { 
                match self.next { 
                    None => return false,
                    _ => *self = *self.next.take().unwrap(),
                }
                true
            } else { 
                let mut index = 0;
                let mut ptr = self;
                while index < idx - 1 { 
                    match ptr.next { 
                        None => return false,
                        Some(ref mut tmp) => { 
                            ptr = tmp;
                        }
                    }
                    index += 1;
                }
                match ptr.next { 
                    None => return false,
                    Some(ref mut tmp) => { 
                        match tmp.next { 
                            None => ptr.next = None,
                            _ => *tmp = Box::new(*tmp.next.take().unwrap()),
                        }
                    }
                }
                true
            }
        }
    }
    
    fn main() { 
        let mut a = Node::from(&[1, 2, 3, 4, 5, 6]);
        println!("{:#?}", a);
        print!("{}", a.delete(0));
        println!("{:#?}", a);
    }