節點的結構

希望鏈表存盤在堆上，所以使用 Box 包裹節點 Rust 沒有空值，所以用 Option 在包裹一層

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

根據索引查找節點和找尾節點是通過遞回來查找的

impl<T> ListNode<T> {
    // 新建一個節點
    #[inline]
    fn new(data: T) -> ListNode<T> {
        ListNode { next: None, data }
    }
    // 獲取最后的節點
    fn get_last_node<'a>(&'a mut self) -> &'a mut Self {
        if let Some(ref mut node) = self.next {
            return node.get_last_node();
        }
        self
    }
    // 根據索引查找節點
    fn get_index_node<'a>(&'a mut self, cur: usize, index: usize) -> &'a mut Self {
        if cur >= index {
            return self;
        }
        if let Some(ref mut node) = self.next {
            return node.get_index_node(cur + 1, index);
        }
        self
    }
}

鏈表的結構

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

鏈表插入

鏈表的插入先判斷頭結點是否為空，如果插入的是頭結點的話，需要將新的節點的下個節點設定為頭結點，再將新結點設定為頭節點，插入的是其他的位置的話，先找到索引的前一個節點，將前一個節點的下個節點設定為新節點，將新節點的下個節點設定為前節點的下個節點，

// 插入
fn insert(&mut self, index: usize, data: T) {
    let mut new_node = ListNode::new(data);
    if let Some(ref mut head) = self.head {
        if index == 0 {
            let head = self.head.take();
            new_node.next = head;
            self.head = Some(Box::new(new_node));
        } else {
            let mut prev_node = head.get_index_node(0, index - 1);
            let next_node = prev_node.next.take();
            new_node.next = next_node;
            prev_node.next = Some(Box::new(new_node));
        }
    } else {
        self.head = Some(Box::new(new_node));
    }
    self.length += 1
}

鏈表洗掉

// 洗掉
    fn delete(&mut self, index: usize) {
        if let Some(ref mut head) = self.head {
            self.length -= 1;
            if index == 0 {
                self.head = head.next.take();
            } else if index >= self.length {
                let prev_node = head.get_index_node(0, self.length - 1);
                prev_node.next.take();
            } else {
                let mut prev_node = head.get_index_node(0, index - 1);
                let mut next_node = prev_node.next.take();
                prev_node.next = next_node.as_mut().unwrap().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;
            }
            let mut node = head.get_index_node(0, index);
            node.data = https://www.cnblogs.com/noobhukai/archive/2022/01/02/data;
        }
    }
    //  查詢
    fn search(&mut self, index: usize) -> Option {
        if let Some(ref mut head) = self.head {
            if index >= self.length {
                return None;
            }
            let node = head.get_index_node(0, index);
            let data = node.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 {
            let mut head = Some(head);
            while let Some(node) = head {
                write!(f, "{:?} => ", node.data).unwrap();
                head = node.next.as_ref();
            }
        }
        write!(f, "None")
    }
}

代碼地址

標籤：其他

上一篇：ingress-nginx 部署使用

下一篇：生成對抗網路GAN與DCGAN的理解