toolbox_rs/
single_linked_list.rs

1use std::{cmp::PartialOrd, fmt::Debug};
2
3#[derive(Debug)]
4struct Node<T> {
5    next: Option<Box<Node<T>>>,
6    elem: T,
7}
8
9pub struct SingleLinkedList<T> {
10    head: Option<Box<Node<T>>>,
11}
12
13impl<T: Copy + Debug + PartialOrd> SingleLinkedList<T> {
14    pub fn new() -> Self {
15        Self { head: None }
16    }
17
18    pub fn push_front(&mut self, elem: T) {
19        let new_node = Box::new(Node {
20            next: self.head.take(),
21            elem,
22        });
23        self.head = Some(new_node);
24    }
25
26    pub fn pop_front(&mut self) -> Option<T> {
27        self.head.take().map(|node| {
28            self.head = node.next;
29            node.elem
30        })
31    }
32
33    pub fn peek_front(&self) -> Option<&T> {
34        self.head.as_ref().map(|node| &node.elem)
35    }
36
37    pub fn peek_front_mut(&mut self) -> Option<&mut T> {
38        self.head.as_mut().map(|node| &mut node.elem)
39    }
40
41    pub fn is_empty(&self) -> bool {
42        self.head.is_none()
43    }
44
45    pub fn is_sorted(&self) -> bool {
46        let mut current = &self.head;
47        while let Some(node) = current {
48            if let Some(next_node) = &node.next {
49                if node.elem > next_node.elem {
50                    return false;
51                }
52            }
53            current = &node.next;
54        }
55        true
56    }
57
58    // Insert an element in a descendengly sorted linked list
59    pub fn insert_sorted(&mut self, elem: T) {
60        let mut current = &mut self.head;
61        while let Some(node) = current {
62            let next_is_smaller = match &node.next {
63                Some(next) => next.elem < elem,
64                None => false,
65            };
66
67            if next_is_smaller {
68                current = &mut node.next;
69            } else {
70                let new_node = Box::new(Node {
71                    next: node.next.take(),
72                    elem,
73                });
74                node.next = Some(new_node);
75                return;
76            }
77        }
78    }
79}
80
81impl<T: Copy + Debug + PartialOrd> Default for SingleLinkedList<T> {
82    fn default() -> Self {
83        Self::new()
84    }
85}
86
87#[cfg(test)]
88mod test {
89    #[test]
90    fn creation_push_peek_pop() {
91        let mut list = super::SingleLinkedList::new();
92        assert_eq!(list.is_empty(), true);
93        list.push_front(1);
94        list.push_front(2);
95        list.push_front(3);
96        assert_eq!(list.is_empty(), false);
97        assert_eq!(list.peek_front(), Some(&3));
98        assert_eq!(list.peek_front_mut(), Some(&mut 3));
99        assert_eq!(list.pop_front(), Some(3));
100        assert_eq!(list.pop_front(), Some(2));
101        assert_eq!(list.pop_front(), Some(1));
102        assert_eq!(list.pop_front(), None);
103        assert_eq!(list.is_empty(), true);
104    }
105
106    #[test]
107    fn find_not_less() {
108        let mut list = super::SingleLinkedList::new();
109        assert_eq!(list.is_empty(), true);
110        assert!(list.is_sorted());
111        list.push_front(8);
112        list.push_front(5);
113        list.push_front(1);
114        assert!(list.is_sorted());
115
116        list.insert_sorted(3);
117        list.insert_sorted(2);
118        assert!(list.is_sorted());
119        list.insert_sorted(6);
120        list.insert_sorted(4);
121        list.insert_sorted(7);
122        list.insert_sorted(9);
123    }
124
125    #[test]
126    fn unsorted() {
127        let mut list = super::SingleLinkedList::default();
128        assert_eq!(list.is_empty(), true);
129        assert!(list.is_sorted());
130        list.push_front(5);
131        list.push_front(8);
132        list.push_front(1);
133        assert!(!list.is_sorted());
134    }
135}
toolbox_rs/single_linked_list.rs

toolbox_rs/
single_linked_list.rs
