sorted_linked_list/
lib.rs

1use std::fmt::Display;
2use std::fmt::Formatter;
3
4struct Node {
5    value: i32,
6    next: Option<Box<Node>>,
7}
8
9pub struct SortedLinkedList {
10    head: Option<Box<Node>>,
11    count: usize,
12}
13
14pub struct Iter<'a> {
15    next: Option<&'a Node>,
16}
17impl Node {
18    fn new(value: i32, next: Option<Box<Node>>) -> Self {
19        Node { value, next }
20    }
21}
22
23impl Default for SortedLinkedList {
24    fn default() -> Self {
25        Self::new()
26    }
27}
28
29impl SortedLinkedList {
30    pub fn new() -> Self {
31        SortedLinkedList {
32            head: Option::None,
33            count: 0,
34        }
35    }
36
37    pub fn add_item(&mut self, item: i32) {
38        let mut curr = &mut self.head;
39        while let Some(node) = curr
40            && node.value < item
41        {
42            curr = &mut curr.as_mut().unwrap().next;
43        }
44        let old_tail = curr.take();
45
46        *curr = Some(Box::new(Node::new(item, old_tail)));
47        self.count += 1;
48    }
49
50    pub fn delete_value(&mut self, item: i32) {
51        let mut curr = &mut self.head;
52        while curr.is_some() && curr.as_ref().unwrap().value != item {
53            curr = &mut curr.as_mut().unwrap().next;
54        }
55        if curr.is_none() {
56            return;
57        }
58        if let Some(mut old_node) = curr.take() {
59            *curr = old_node.next.take();
60            self.count -= 1;
61        }
62    }
63
64    pub fn iter(&self) -> Iter<'_> {
65        Iter {
66            next: self.head.as_deref(),
67        }
68    }
69}
70
71impl Display for SortedLinkedList {
72    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
73        write!(f, "[")?;
74        let mut first = true;
75        for val in self.iter() {
76            if !first {
77                write!(f, ", ")?;
78            }
79            write!(f, "{}", val)?;
80            first = false;
81        }
82        write!(f, "]")?;
83        Ok(())
84    }
85}
86
87impl<'a> Iterator for Iter<'a> {
88    type Item = &'a i32;
89    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
90        self.next.map(|node| {
91            self.next = node.next.as_deref();
92            &node.value
93        })
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn sorted_corr() {
103        let mut sll = SortedLinkedList::new();
104        sll.add_item(23);
105        sll.add_item(24);
106        sll.add_item(22);
107        sll.add_item(23);
108        assert!(format!("{}", sll) == "[22, 23, 23, 24]")
109    }
110    #[test]
111    fn deletion() {
112        let mut sll = SortedLinkedList::new();
113        sll.add_item(23);
114        sll.add_item(24);
115        sll.add_item(22);
116        sll.delete_value(22);
117        assert!(format!("{}", sll) == "[23, 24]")
118    }
119}
sorted_linked_list/lib.rs

sorted_linked_list/
lib.rs
