節點的結構

1. 指向節點的指標可能為空值，所以在最外層包裹一層 Option
2. 一個節點可能存在被兩個指標指向（前一個節點的 next 和后一個節點的 prev），指標需要用 Rc 包裹，
3. Rc指標指向的值默認情況下是不可以修改的，只讀性質，可以通過RefCell指標修改其內部的值

#[derive(PartialEq, Eq, Clone, Debug)]
struct ListNode<T> {
    pub data: T,
    pub next: Option<Rc<RefCell<ListNode<T>>>>,
    pub prev: Option<Rc<RefCell<ListNode<T>>>>,
}

節點函式

節點的列印函式是通過不斷的遞回來實作的

impl<T: Debug> ListNode<T> {
    #[inline]
    fn new(data: T) -> ListNode<T> {
        ListNode {
            data,
            prev: None,
            next: None,
        }
    }
    fn display(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?} => ", self.data)?;
        if let Some(node) = &self.next {
            return node.borrow().display(f);
        }
        write!(f, "")
    }
}

查找節點函式

fn get_index_node<T>(
    node: Rc<RefCell<ListNode<T>>>,
    cur: usize,
    index: usize,
) -> Rc<RefCell<ListNode<T>>> {
    if cur >= index {
        return node;
    }
    if let Some(node1) = &node.borrow_mut().next {
        let a = get_index_node(node1.clone(), cur + 1, index);
        return a.clone();
    }
    return node;
}

鏈表的結構

#[derive(PartialEq, Eq, Clone, Debug)]
struct List<T> {
    pub head: Option<Rc<RefCell<ListNode<T>>>>,
    pub length: usize,
}

impl<T: Debug + Copy> List<T> {
    #[inline]
    fn new() -> Self {
        List {
            head: None,
            length: 0,
        }
    }
}

插入

插入需要先判斷頭結點是否為空，還需要判斷插入的位置，

fn insert(&mut self, index: usize, data: T) {
	let mut new_node = ListNode::new(data);
    self.length += 1;
    if let Some(ref mut head) = self.head {
        if index == 0 {
                let head = self.head.take().unwrap();
                new_node.next = Some(head.clone());
                let rc = Rc::new(RefCell::new(new_node));
                head.borrow_mut().prev = Some(rc.clone());
                self.head = Some(rc);
            } else {
                let prev_node = get_index_node(head.clone(), 0, index - 1);
                new_node.next = prev_node.borrow_mut().next.take();
                prev_node.clone().borrow_mut().next = Some(Rc::new(RefCell::new(new_node)));
            }
        } else {
            self.head = Some(Rc::new(RefCell::new(new_node)))
        }
    }

洗掉

   fn delete(&mut self, index: usize) {
        if let Some(ref mut head) = self.head {
            self.length -= 1;
            if index == 0 {
                self.head = head.clone().borrow_mut().next.take();
            } else if index >= self.length {
                let prev_node = get_index_node(head.clone(), 0, self.length - 1);
                prev_node.borrow_mut().next.take();
            } else {
                let prev_node = get_index_node(head.clone(), 0, index - 1);
                let mut next_node = prev_node.borrow_mut().next.take();
                prev_node.borrow_mut().next = next_node.as_mut().unwrap().borrow_mut().next.take();
            }
        }
    }

修改

fn change(&mut self, mut index: usize, data: T) {
        if let Some(ref mut head) = self.head {
            if index >= self.length {
                index = self.length;
            }
            get_index_node(head.clone(), 0, index).borrow_mut().data = https://www.cnblogs.com/noobhukai/archive/2022/01/04/data;
        }
    }

查詢

因為查詢在這里只是 Copy出去，泛型是需要實作 Copy

fn search(&mut self, index: usize) -> Option<T> {
        if let Some(ref mut head) = self.head {
            if index >= self.length {
                return None;
            }
            let data = https://www.cnblogs.com/noobhukai/archive/2022/01/04/get_index_node(head.clone(), 0, index).borrow().data;
            return Some(data);
        } else {
            return None;
        }
    }

列印

impl<T> Display for List<T>
where
    T: Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if let Some(head) = &self.head {
            head.borrow().display(f)?
        }
        write!(f, "None")
    }
}

代碼地址

標籤：其他

上一篇：快速上手SpringMVC

下一篇：Java三大特性之多型