節(jié)點(diǎn)的結(jié)構(gòu)

希望鏈表存儲(chǔ)在堆上，所以使用 Box 包裹節(jié)點(diǎn) Rust 沒有空值，所以用 Option 在包裹一層

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

根據(jù)索引查找節(jié)點(diǎn)和找尾節(jié)點(diǎn)是通過遞歸來查找的

impl<T> ListNode<T> {
    // 新建一個(gè)節(jié)點(diǎn)
    #[inline]
    fn new(data: T) -> ListNode<T> {
        ListNode { next: None, data }
    }
    // 獲取最后的節(jié)點(diǎn)
    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
    }
    // 根據(jù)索引查找節(jié)點(diǎn)
    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
    }
}

鏈表的結(jié)構(gòu)

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

鏈表插入

鏈表的插入先判斷頭結(jié)點(diǎn)是否為空。如果插入的是頭結(jié)點(diǎn)的話，需要將新的節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)設(shè)置為頭結(jié)點(diǎn)，再將新結(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)。插入的是其他的位置的話，先找到索引的前一個(gè)節(jié)點(diǎn)，將前一個(gè)節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)設(shè)置為新節(jié)點(diǎn)，將新節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)設(shè)置為前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)。

// 插入
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 = data;
        }
    }
    //  查詢
    fn search(&mut self, index: usize) -> Option<T> {
        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")
    }
}

代碼地址