节点的结构

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 = 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 = 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")
    }
}

代码地址