structure of node

1. The index pointing to the node may be empty, so wrap a layer of Option
in the outermost layer
2. A node may be pointed to by two indicators (next of the previous node and prev of the next node), the indicator needs to use Rc package,
3. The value pointed to by the Rc indicator cannot be modified by default, it is read-only, and its internal value can be modified through the RefCell indicator

#[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>>>>,
}

node function

The print function of the node is implemented by repeatedly returning it

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

find node function

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;
}

structure of linked list

#[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,
        }
    }
}

insert

In insertion, it is necessary to first determine whether the header node is empty, and also need to determine the insertion position,

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

wash off

 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();
            }
        }
    }

modify

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;
        }
    }

query

Because the query here is just Copy out, generics need to implement 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;
        }
    }

print

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

Code address