乱up廿四

早知道,还是std::collections::LinkedList!

本文部分使用了chatgpt辅助,所以如果有错,不全是我的锅(

Safe Rust的批判

总所周知,Rust的卖点就是所有权,借用检查,生命周期等等,但是这些特性在实现链表的时候会增添许多麻烦

比如一个safe的定义:

pub struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    len: usize,
}

如果你只是独占地使用该定义的链表是没什么问题的,这里的独占指的就是只有一个东西拥有链表的所有权.比如常规的头插尾插,以及删改查都是可以的

但如果你一旦要整点骚操作,safe rust就会开始刁难你了

比如你想要同时使用双指针遍历,因为遍历需要把变量赋值到next以实现移动,所以你需要创建2个类型为&mut Option<Box<Node<T>>>的变量. 同时使用多个可变引用在safe rust是不可能的,所以没门.你只能一个一个地使用可变引用遍历,也就是说可变引用的作用域不能重叠

比如leetcode的一个链表题,要求你找出倒数前k个节点的值,在safe rust你只能先用一个可变引用算出链表的长度n,然后再用一个可变引用遍历到n-k的地方

再有就是多个节点指向同一个节点的情况,在 Rust 中,每个 Box 对象都拥有唯一的所有权,也即是只能有一个指针指向它.因此,如果我们尝试将多个节点指向同一个节点,编译器将会报错,比如下面的布局

list1 -> A ---+
              |
              v
list2 ------> C -> D
              ^
              |
list3 -> B ---+

用上面的定义创建就会报错

这时候网上教程会建议你使用Option<Rc<Node<T>>来实现多个节点之间共享数据的情况, Rc 代表引用计数

你可能会想,为什么不用&Option<Box<Node<T>>>呢?

Rc 和 &Box 都将底层数据存储在堆上,都不能跨线程发送,并且都是不可变共享.然而,最大的区别是 Rc 给你一个共享的（不可变的）拥有所有权的值,而 &Box 你得到一个共享的（不可变的）引用

在 Rc (引用计数)的情况下,只有最后一个所有者被删除,底层数据才会被删除(不然只删除智能指针并减少引用计数)

然而, &Box 只会有一个所有者,在所有者离开范围后,对它的任何共享引用都将立即失效.

https://stackoverflow.com/questions/49377231/when-to-use-rc-vs-box

所以 &Box 没法保证共享引用是有效的,当然,这个问题会在编译期就暴露出来,懂不懂生命周期的威力啊?(

再有, &Option<Box<Node<T>>>这个类型和Option<Box<Node<T>>>是不一样的,你链表里没法填上去

那把链表定义也改了呢?你就会发现还需要标注生命周期,就像这样:

pub struct Node<'a, T> {
    data: T,
    next: &'a Option<Box<Node<'a, T>>>,
}

pub struct LinkedList<'a, T> {
    head: &'a Option<Box<Node<'a, T>>>,
    len: usize,
}

好歹编译器没意见了,但其实这也是个巨坑.使用 &Option<Box<Node<T>>> 会将指针放在栈上,而节点数据仍然存储在堆上,这意味着我们需要手动管理节点的生命周期和内存分配,标生命周期就能整得脑溢血.其次, &Option<Box<Node<T>>> 只能使用引用语义而不能使用值语义,有事没事就得解引用*,而且如果想可变又得改成&mut Option<Box<Node<T>>>, 又有一堆问题. 虽然Rc也不能可变(

safe rust最后会变成这样:

use std::rc::Rc;
use std::cell::RefCell;

pub struct Node<T> {
    data: T,
    next: Option<Rc<RefCell<Node<T>>>>,
}

pub struct LinkedList<T> {
    head: Option<Rc<RefCell<Node<T>>>>,
    size: usize,
}

在这里,使用 Rc 类型来实现多个节点之间共享数据,使用 RefCell 类型来提供内部可变性

这样我们就可以在不使用可变引用的情况下修改节点的值了:

let node = Rc::new(RefCell::new(Node { data: 42, next: None }));
node.borrow_mut().data = 100;

虽然但是,用了Rc和 RefCell 并不意味着你就摆脱了safe rust的种种限制了,比如所有权,你仍然不能同时拥有多个可变引用.虽然现在编译期不会报错了,但是会延后到运行期(

G!

所以说了这么多,结论就是:safe rust没有办法处理同时拥有多个可变引用的问题,而且涉及多个节点指向同一个节点的情况会很麻烦(如果是循环引用,Rc还不足以解决问题,还需要一个Weak指针)

Unsafe Rust的单向链表实现

基本定义和实现

所以链表还是得用裸指针定义:

use std::ptr;

pub struct LinkedList<T> {
    len: usize,
    head: *mut Node<T>,
    tail: *mut Node<T>,
}

pub struct Node<T> {
    data: T,
    next: *mut Node<T>,
}

全用可变裸指针,就像C一样(

PS. 不要一些用裸指针,一些不用.要用就全用.

将安全的指针 & 、&mut 和 Box 跟不安全的裸指针 *mut 和 *const 混用是 UB 的根源之一,原因是安全指针会引入额外的约束,但是裸指针并不会遵守这些约束

https://rust-unofficial.github.io/too-many-lists/fifth-layout-basics-redux.html

这里的链表有头和尾指针,而且没有虚拟节点(dummy node).虽然有虚拟节点可以不用管一些边界条件,但是Rust没有办法设置虚拟节点的值(除非你规定T有一个默认值).data改用Option<T>可以解决这个问题,但是代价是基本全部代码都要处理Some和None的情况,巨麻烦

Node的方法实现:

impl<T> Node<T> {
    pub fn new(data: T) -> Node<T> {
        Node {
            data,
            next: ptr::null_mut(),
        }
    }
}

然后是链表本体,首先来点简单的:

impl<T> LinkedList<T> { //后面有关LinkedList<T>的方法不再用impl块包着,不然太麻烦
	pub fn new() -> LinkedList<T> {
        LinkedList {
            len: 0,
            head: ptr::null_mut(),
            tail: ptr::null_mut(),
        }
    }
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }
    pub fn len(&self) -> usize {
        self.len
    }
}

然后是头插和尾插:

 	pub fn push_front(&mut self, data: T) {
        let mut new_node = Box::into_raw(Box::new(Node::new(data)));
        if self.is_empty() {
            self.tail = new_node;
        } else {
            unsafe {
                (*new_node).next = self.head;
            }
        }
        self.head = new_node;
        self.len += 1;
    }
    pub fn push_back(&mut self, data: T) {
        let new_node = Box::into_raw(Box::new(Node::new(data)));
        if self.is_empty() {
            self.head = new_node;
        } else {
            unsafe {
                (*self.tail).next = new_node;
            }
        }
        self.tail = new_node;
        self.len += 1;
    }

第2行创建新节点,rust可以用std::alloc::alloc来申请内存,就像C的malloc或者C++的new,但有更舒服的方法

pub fn into_raw(b: Box<T>) -> *mut T

消费掉 Box (拿走所有权),返回一个裸指针.该指针会被正确的对齐且不为 null

在调用该函数后,调用者需要对之前被 Box 所管理的内存负责,特别地,调用者需要正确的清理 T 并释放相应的内存.最简单的方式是通过 Box::from_raw 函数将裸指针再转回到 Box,然后 Box 的析构器就可以自动执行清理了.

所以我们先用 Box::new() 申请内存,把node放进去,然后再转成裸指针形式

中间有一些边界处理,没用虚拟节点是这样的.其他部分和C/C++差不多

头删和尾删:

    pub fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let old_head = self.head;
        unsafe {
            self.head = (*self.head).next;
        }
        self.len -= 1;
        if self.is_empty() {
            self.tail = ptr::null_mut();
        }
        Some(unsafe { Box::from_raw(old_head).data })
    }
    pub fn pop_back(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let mut curr = self.head;
        let mut prev = ptr::null_mut();
        // let curr go to the end of the list
        // and prev go to the node before curr
        while unsafe { !(*curr).next.is_null() } {
            prev = curr;
            unsafe {
                curr = (*curr).next;
            }
        }
        self.tail = prev;
        // if prev is null, it means that curr is the only node in the list
        if prev.is_null() {
            self.head = ptr::null_mut();
        } else {
            unsafe {
                (*prev).next = ptr::null_mut();
            }
        }
        self.len -= 1;
        Some(unsafe { Box::from_raw(curr).data })
    }

13行,因为pop返回T本身,所有权会交出去,那谁管理T的内存?还是得交给Box

如果你写Some(unsafe { (*old_head).data }),编译器不让你把data移出去,因为没人管理内存了,除非你clone一份

19-28行,也只有unsafe rust能做这种操作

然后是获得引用的一些方法:

    pub fn peek_front(&self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }
        Some(unsafe { &(*self.head).data })
    }
    pub fn peek_back(&self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }
        Some(unsafe { &(*self.tail).data })
    }
    pub fn get(&self, index: usize) -> Option<&T> {
        if index >= self.len {
            return None;
        }
        let mut curr = self.head;
        for _ in 0..index {
            unsafe {
                curr = (*curr).next;
            }
        }
        Some(unsafe { &(*curr).data })
    }
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index >= self.len {
            return None;
        }
        let mut curr = self.head;
        for _ in 0..index {
            unsafe {
                curr = (*curr).next;
            }
        }
        Some(unsafe { &mut (*curr).data })
    }

这时候因为是返回引用,内存还是链表来管,所以就不用Box::into_raw

然后是往指定索引处插入/删除:

    pub fn insert_at(&mut self, index: usize, data: T) -> bool {
        if index > self.len {
            return false;
        }
        // edge cases, because there is no dummy node
        if index == 0 {
            self.push_front(data);
            return true;
        }
        if index == self.len {
            self.push_back(data);
            return true;
        }

        let mut curr = self.head;
        let mut prev = ptr::null_mut();
        for _ in 0..index {
            prev = curr;
            unsafe {
                curr = (*curr).next;
            }
        }
        let new_node = Box::into_raw(Box::new(Node::new(data)));
        unsafe {
            (*prev).next = new_node;
            (*new_node).next = curr;
        }
        self.len += 1;
        true
    }
    pub fn remove_at(&mut self, index: usize) -> Option<T> {
        if index >= self.len {
            return None;
        }
        // edge cases, because there is no dummy node
        if index == 0 {
            return self.pop_front();
        }
        if index == self.len - 1 {
            return self.pop_back();
        }

        let mut curr = self.head;
        let mut prev = ptr::null_mut();
        for _ in 0..index {
            prev = curr;
            unsafe {
                curr = (*curr).next;
            }
        }
        unsafe {
            (*prev).next = (*curr).next;
        }
        self.len -= 1;
        Some(unsafe { Box::from_raw(curr).data })
    }

还是因为没有虚拟节点,多了很多if判断边界

Drop的实现

虽说rust会帮你释放内存,但是它是一层层调用drop去释放的,这导致在链表下,rust需要递归调用到最后一个节点才能去释放,是倒着释放的,这有可能会爆栈(rust不支持尾递归).而我们知道链表可以一直头删来实现释放,所以我们要自己实现drop

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop_front() {}
    }
}

甚至不需要显式调用drop()

花活:实现迭代器

rust的迭代器也是一大特色,可以很舒服的处理集合中的元素.链表的遍历也可以实现为迭代器

pub struct IntoIter<T>(LinkedList<T>);
impl<T> IntoIterator for LinkedList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}
impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop_front()
    }
}

into_iter需要所有权,最简单的方法就是用一个struct保住原来的

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}
impl<T> LinkedList<T> {
    pub fn iter(&self) -> Iter<T> {
        unsafe {
            Iter {
                next: self.head.as_ref(),
            }
        }
    }
}
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        // map is used to convert the Option<&Node<T>> to Option<&T>, if the Option is None, it will return None
        self.next.map(|node| {
            self.next = unsafe { node.next.as_ref() };
            &node.data
        })
    }
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}
impl<T> LinkedList<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        unsafe {
            IterMut {
                next: self.head.as_mut(),
            }
        }
    }
}
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = unsafe { node.next.as_mut() };
            &mut node.data
        })
    }
}

而iter和iter_mut只需要元素的引用,不需要拿到链表的所有权,所以我们这里只设置一个成员next,用来记录目前引用的元素,而且单靠next就可以移动到下一个节点

这里需要生命周期标注,因为Node能活多久,其他的struct是不知道的.我们标注的意思就是告诉编译器:Node至少和其他struct活得一样久.也就是说其他struct能肯定自己的引用肯定有效

结束!

最后,链表其实用的不多,可惜有人就爱出这些题

其次,我讨厌链表.链表真的是一种糟糕的数据结构,尽管它在部分场景下确实很有用：

• 对列表进行大量的分割和合并操作
• 无锁并发
• 要实现内核或嵌入式的服务
• 你在使用一个纯函数式语言,由于受限的语法和缺少可变性,因此你需要使用链表来解决这些问题

但是实事求是的说,这些场景对于几乎任何 Rust 开发都是很少遇到的,99% 的场景你可以使用 Vec 来替代,然后 1% 中的 99% 可以使用 VecDeque. 由于它们具有更少的内存分配次数、更低的内存占用、随机访问和缓存亲和特性,因此能够适用于绝大多数工作场景.总之,类似于 trie 树,链表也是一种非常小众的数据结构,特别是对于 Rust 开发而言.

https://course.rs/too-many-lists/do-we-need-it.html

本书只是为了学习链表该如何实现,如果大家只是为了使用链表,强烈推荐直接使用标准库或者社区提供的现成实现,例如 std::collections::LinkedList

全部代码以及测试用例

use std::ptr;

#[derive(Debug)]
pub struct LinkedList<T> {
    len: usize,
    head: *mut Node<T>,
    tail: *mut Node<T>,
}

pub struct Node<T> {
    data: T,
    next: *mut Node<T>,
}

impl<T> Node<T> {
    pub fn new(data: T) -> Node<T> {
        Node {
            data,
            next: ptr::null_mut(),
        }
    }
}

impl<T> LinkedList<T> {
    pub fn new() -> LinkedList<T> {
        LinkedList {
            len: 0,
            head: ptr::null_mut(),
            tail: ptr::null_mut(),
        }
    }
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }
    pub fn len(&self) -> usize {
        self.len
    }
    pub fn push_front(&mut self, data: T) {
        let mut new_node = Box::into_raw(Box::new(Node::new(data)));
        if self.is_empty() {
            self.tail = new_node;
        } else {
            unsafe {
                (*new_node).next = self.head;
            }
        }
        self.head = new_node;
        self.len += 1;
    }
    pub fn push_back(&mut self, data: T) {
        let new_node = Box::into_raw(Box::new(Node::new(data)));
        if self.is_empty() {
            self.head = new_node;
        } else {
            unsafe {
                (*self.tail).next = new_node;
            }
        }
        self.tail = new_node;
        self.len += 1;
    }
    pub fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let old_head = self.head;
        unsafe {
            self.head = (*self.head).next;
        }
        self.len -= 1;
        if self.is_empty() {
            self.tail = ptr::null_mut();
        }
        Some(unsafe { Box::from_raw(old_head).data })
    }
    pub fn pop_back(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let mut curr = self.head;
        let mut prev = ptr::null_mut();
        // let curr go to the end of the list
        // and prev go to the node before curr
        while unsafe { !(*curr).next.is_null() } {
            prev = curr;
            unsafe {
                curr = (*curr).next;
            }
        }
        self.tail = prev;
        // if prev is null, it means that curr is the only node in the list
        if prev.is_null() {
            self.head = ptr::null_mut();
        } else {
            unsafe {
                (*prev).next = ptr::null_mut();
            }
        }
        self.len -= 1;
        Some(unsafe { Box::from_raw(curr).data })
    }
    pub fn peek_front(&self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }
        Some(unsafe { &(*self.head).data })
    }
    pub fn peek_back(&self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }
        Some(unsafe { &(*self.tail).data })
    }
    pub fn get(&self, index: usize) -> Option<&T> {
        if index >= self.len {
            return None;
        }
        let mut curr = self.head;
        for _ in 0..index {
            unsafe {
                curr = (*curr).next;
            }
        }
        Some(unsafe { &(*curr).data })
    }
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index >= self.len {
            return None;
        }
        let mut curr = self.head;
        for _ in 0..index {
            unsafe {
                curr = (*curr).next;
            }
        }
        Some(unsafe { &mut (*curr).data })
    }
    pub fn insert_at(&mut self, index: usize, data: T) -> bool {
        if index > self.len {
            return false;
        }
        // edge cases, because there is no dummy node
        if index == 0 {
            self.push_front(data);
            return true;
        }
        if index == self.len {
            self.push_back(data);
            return true;
        }

        let mut curr = self.head;
        let mut prev = ptr::null_mut();
        for _ in 0..index {
            prev = curr;
            unsafe {
                curr = (*curr).next;
            }
        }
        let new_node = Box::into_raw(Box::new(Node::new(data)));
        unsafe {
            (*prev).next = new_node;
            (*new_node).next = curr;
        }
        self.len += 1;
        true
    }
    pub fn remove_at(&mut self, index: usize) -> Option<T> {
        if index >= self.len {
            return None;
        }
        // edge cases, because there is no dummy node
        if index == 0 {
            return self.pop_front();
        }
        if index == self.len - 1 {
            return self.pop_back();
        }

        let mut curr = self.head;
        let mut prev = ptr::null_mut();
        for _ in 0..index {
            prev = curr;
            unsafe {
                curr = (*curr).next;
            }
        }
        unsafe {
            (*prev).next = (*curr).next;
        }
        self.len -= 1;
        Some(unsafe { Box::from_raw(curr).data })
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop_front() {}
    }
}

// into_iter needs the ownership of the list, so we just wrap it in a struct
pub struct IntoIter<T>(LinkedList<T>);
impl<T> IntoIterator for LinkedList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}
impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop_front()
    }
}

//iter doesn't have ownership of the list, so we need "next" to record the next reference node
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}
impl<T> LinkedList<T> {
    pub fn iter(&self) -> Iter<T> {
        unsafe {
            Iter {
                next: self.head.as_ref(),
            }
        }
    }
}
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        // map is used to convert the Option<&Node<T>> to Option<&T>, if the Option is None, it will return None
        self.next.map(|node| {
            self.next = unsafe { node.next.as_ref() };
            &node.data
        })
    }
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}
impl<T> LinkedList<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        unsafe {
            IterMut {
                next: self.head.as_mut(),
            }
        }
    }
}
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = unsafe { node.next.as_mut() };
            &mut node.data
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_push_front() {
        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        assert_eq!(list.len(), 3);
        assert_eq!(list.peek_front(), Some(&3));
        assert_eq!(list.peek_back(), Some(&1));
    }

    #[test]
    fn test_push_back() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.len(), 3);
        assert_eq!(list.peek_front(), Some(&1));
        assert_eq!(list.peek_back(), Some(&3));
    }

    #[test]
    fn test_pop_front() {
        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
    }

    #[test]
    fn test_pop_back() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn test_peek_front() {
        let mut list = LinkedList::new();
        assert_eq!(list.peek_front(), None);
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        assert_eq!(list.peek_front(), Some(&3));
    }

    #[test]
    fn test_peek_back() {
        let mut list = LinkedList::new();
        assert_eq!(list.peek_back(), None);
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.peek_back(), Some(&3));
    }

    #[test]
    fn test_get() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.get(0), Some(&1));
        assert_eq!(list.get(1), Some(&2));
        assert_eq!(list.get(2), Some(&3));
        assert_eq!(list.get(3), None);
    }

    #[test]
    fn test_get_mut() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.get_mut(0), Some(&mut 1));
        assert_eq!(list.get_mut(1), Some(&mut 2));
        assert_eq!(list.get_mut(2), Some(&mut 3));
        assert_eq!(list.get_mut(3), None);
        if let Some(x) = list.get_mut(0) {
            *x = 10;
        }
        assert_eq!(list.get(0), Some(&10));
    }

    #[test]
    fn test_insert_at() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        list.insert_at(0, 10);
        assert_eq!(list.get(0), Some(&10));
        assert_eq!(list.get(1), Some(&1));
        assert_eq!(list.get(2), Some(&2));
        assert_eq!(list.get(3), Some(&3));
        list.insert_at(1, 20);
        assert_eq!(list.get(0), Some(&10));
        assert_eq!(list.get(1), Some(&20));
        assert_eq!(list.get(2), Some(&1));
        assert_eq!(list.get(3), Some(&2));
        assert_eq!(list.get(4), Some(&3));
        list.insert_at(5, 30);
        assert_eq!(list.get(0), Some(&10));
        assert_eq!(list.get(1), Some(&20));
        assert_eq!(list.get(2), Some(&1));
        assert_eq!(list.get(3), Some(&2));
        assert_eq!(list.get(4), Some(&3));
        assert_eq!(list.get(5), Some(&30));
    }

    #[test]
    fn test_remove_at() {
        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        list.push_front(4);
        list.push_front(5);
        //5 4 3 2 1
        assert_eq!(list.remove_at(0), Some(5)); //4 3 2 1
        assert_eq!(list.remove_at(1), Some(3)); //4 2 1
        assert_eq!(list.remove_at(2), Some(1)); //4 2
        assert_eq!(list.remove_at(3), None);
    }

    // test iterator
    #[test]
    fn test_iter() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }
    #[test]
    fn test_iter_mut() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        for x in list.iter_mut() {
            *x += 1;
        }
        assert_eq!(list.get(0), Some(&2));
        assert_eq!(list.get(1), Some(&3));
        assert_eq!(list.get(2), Some(&4));
    }
    #[test]
    fn test_into_iter() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }
}