节点的结构
希望链表存储在堆上,所以使用 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 = 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")
}
}