single linked list

single.rs

struct Node<T> {
    elem: T,
    next: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct List<T> {
    head: Link<T>,
    size: u32,
}

struct IntoIter<T>(List<T>);

struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
    fn new() -> Self {
        List {
            head: None,
            size: 0,
        }
    }

    fn push(&mut self, elem: T) {
        self.size += 1;
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn pop(&mut self) -> Option<T> {
        match self.head.take() {
            None => None,
            Some(node) => {
                self.size -= 1;
                self.head = node.next;
                Some(node.elem)
            }
        }
    }

    fn top(&self) -> Option<&T> {
        match &self.head {
            None => None,
            Some(node) => Some(&node.elem),
        }
    }

    fn top_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.elem)
    }

    fn is_empty(&self) -> bool {
        match &self.head {
            None => true,
            Some(_) => false,
        }
    }

    fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter {
            next: self.head.as_ref().map(|node| &**node),
        }
    }

    fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
        IterMut {
            next: self.head.as_mut().map(|node| &mut **node),
        }
    }

    fn len(&self) -> u32 {
        self.size
    }

    fn clear(&mut self) {
        self.size = 0;
        self.head = None;
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

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 = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

fn make_list(x: u32) -> List<i32> {
    let mut list = List::new();
    for i in 1..x + 1 {
        list.push(i as i32);
    }
    list
}

#[test]
fn top() {
    let list = make_list(3);
    assert_eq!(list.top(), Some(&3));
}

#[test]
fn top_mut() {
    let mut list = make_list(3);
    assert_eq!(list.top(), Some(&3));
    let x = list.top_mut();
    match x {
        None => {}
        Some(n) => *n += 1,
    }
    assert_eq!(list.top(), Some(&4));
}

#[test]
fn is_empty() {
    let mut list = List::new();
    assert_eq!(list.is_empty(), true);
    list.push(1);
    assert_eq!(list.is_empty(), false);
}

#[test]
fn into_iter() {
    let list = make_list(3);
    let mut iter = list.into_iter();
    assert_eq!(iter.next(), Some(3));
    assert_eq!(iter.next(), Some(2));
    assert_eq!(iter.next(), Some(1));
    assert_eq!(iter.next(), None);
}
#[test]
fn iter() {
    let list = make_list(3);
    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&2));
}

#[test]
fn iter_mut() {
    let mut list = make_list(3);
    let mut iter = list.iter_mut();
    assert_eq!(iter.next(), Some(&mut 3));
    assert_eq!(iter.next(), Some(&mut 2));
    assert_eq!(iter.next(), Some(&mut 1));
}

#[test]
fn len() {
    let mut list = make_list(3);
    assert_eq!(list.len(), 3);
    list.pop();
    assert_eq!(list.len(), 2);
}

#[test]
fn clear() {
    let mut list = make_list(3);
    assert_eq!(list.len(), 3);
    list.clear();
    assert_eq!(list.len(), 0);
}

Rust で Linked List を実装する(1. 単方向連結リスト編)
https://zaki-joho.hatenablog.com/entry/2020/06/17/002513?_ga=2.183796513.648979182.1603959265-1204553321.1534526917