project/datastructures/linear/
sll.rs

1use std::fmt::Debug;
2use std::ptr;
3
4use crate::datastructures::linear::LL;
5use crate::datastructures::nodes::DNode;
6
7/// Implementation of a Singly Linked List.
8pub struct SLL<T> {
9    len: usize,
10    head: *mut DNode<T>,
11    tail: *mut DNode<T>,
12}
13
14impl<T> Default for SLL<T> {
15    fn default() -> Self {
16        Self { len: 0, head: ptr::null_mut(), tail: ptr::null_mut() }
17    }
18}
19
20impl<T> From<Box<DNode<T>>> for SLL<T> {
21    fn from(node: Box<DNode<T>>) -> Self {
22        let node = Box::into_raw(node);
23
24        unsafe {
25            (*node).set_next(ptr::null_mut());
26            (*node).set_prev(ptr::null_mut());
27        }
28
29        Self { len: 1, head: node, tail: node }
30    }
31}
32
33impl<T> LL<T> for SLL<T> {
34    fn len(&self) -> usize {
35        self.len
36    }
37
38    fn head(&self) -> *mut DNode<T> {
39        self.head
40    }
41
42    fn tail(&self) -> *mut DNode<T> {
43        self.tail
44    }
45
46    fn delete_at_index(&mut self, index: usize) -> Option<T> {
47        let len = self.len();
48
49        if len == 0 {
50            None
51        } else if index < len {
52            let mut current_prev = ptr::null_mut();
53            let mut current = self.head;
54
55            for _ in 0..index {
56                current_prev = current;
57                current = unsafe { (*current).get_next() };
58            }
59
60            let (current_data, current_next, _) =
61                unsafe { Box::from_raw(current) }.unpack();
62
63            if !current_prev.is_null() {
64                unsafe { (*current_prev).set_next(current_next) };
65            }
66
67            if index == 0 {
68                self.head = current_next;
69            } else if index == len - 1 {
70                self.tail = current_prev;
71            }
72
73            self.len -= 1;
74
75            Some(current_data)
76        } else {
77            panic!("deletion index (is {index}) should be < len (is {len})");
78        }
79    }
80
81    fn insert(&mut self, data: T, index: usize) {
82        let len = self.len;
83
84        if len == 0 {
85            let node = Box::into_raw(Box::new(DNode::from(data)));
86
87            self.head = node;
88            self.tail = node;
89            self.len += 1;
90        } else if index < len {
91            let mut current_prev = ptr::null_mut();
92            let mut current = self.head;
93
94            for _ in 0..index {
95                current_prev = current;
96                current = unsafe { (*current).get_next() };
97            }
98
99            let node = Box::into_raw(Box::new(DNode::from((
100                data,
101                current,
102                ptr::null_mut(),
103            ))));
104
105            match index {
106                0 => {
107                    self.head = node;
108                },
109                _ => unsafe {
110                    (*current_prev).set_next(node);
111                },
112            }
113
114            self.len += 1;
115        } else if index == len {
116            let node = Box::into_raw(Box::new(DNode::from((
117                data,
118                ptr::null_mut(),
119                ptr::null_mut(),
120            ))));
121
122            unsafe { (*self.tail).set_next(node) };
123
124            self.tail = node;
125            self.len += 1;
126        } else {
127            panic!("insertion index (is {index}) should be <= len (is {len})");
128        }
129    }
130
131    fn print_addresses(&self)
132    where
133        T: Debug,
134    {
135        let mut current = self.head();
136
137        for _ in 0..self.len() {
138            let data = unsafe { (*current).get_data() };
139            let next = unsafe { (*current).get_next() };
140            let prev = unsafe { (*current).get_prev() };
141            println!("{current:?} | data={data:?} next={next:?} prev={prev:?}");
142
143            assert!(!current.is_null());
144            // assert!(prev.is_null() || unsafe { (*prev).get_next() } ==
145            // current); assert!(next.is_null() || unsafe {
146            // (*next).get_prev() } == current);
147
148            current = unsafe { (*current).get_next() };
149        }
150    }
151}
152
153#[cfg(test)]
154mod tests {
155    use super::LL;
156    use super::SLL;
157    use crate::datastructures::nodes::DNode;
158
159    #[test]
160    fn test() {
161        let mut ll = SLL::default();
162
163        ll.insert_head(1);
164        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&1]);
165
166        ll.insert_head(4);
167        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&4, &1]);
168
169        ll.insert_tail(2);
170        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&4, &1, &2]);
171        assert!(!ll.is_sorted());
172
173        ll.insert_sorted(3);
174        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&1, &2, &3, &4]);
175
176        ll.tail();
177        ll.print();
178
179        ll.delete(&3);
180        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&1, &2, &4]);
181
182        ll.clear();
183        assert_eq!(ll.iter_once().count(), 0);
184
185        let mut ll = SLL::from(Box::new(DNode::from(0)));
186        assert_eq!(ll.len(), 1);
187
188        ll.delete_tail();
189    }
190}
project/datastructures/linear/sll.rs

project/datastructures/linear/
sll.rs
