1 //! A singly-linked list.
3 //! Using this data structure only makes sense under very specific
6 //! - If you have a list that rarely stores more than one element, then this
7 //! data-structure can store the element without allocating and only uses as
8 //! much space as a `Option<(T, usize)>`. If T can double as the `Option`
9 //! discriminant, it will even only be as large as `T, usize`.
11 //! If you expect to store more than 1 element in the common case, steer clear
12 //! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`.
14 #[derive(Clone, Hash, Debug, PartialEq)]
15 pub struct TinyList<T: PartialEq> {
16 head: Option<Element<T>>
19 impl<T: PartialEq> TinyList<T> {
22 pub fn new() -> TinyList<T> {
29 pub fn new_single(data: T) -> TinyList<T> {
39 pub fn insert(&mut self, data: T) {
40 self.head = Some(Element {
42 next: self.head.take().map(Box::new)
47 pub fn remove(&mut self, data: &T) -> bool {
48 self.head = match self.head {
49 Some(ref mut head) if head.data == *data => {
50 head.next.take().map(|x| *x)
52 Some(ref mut head) => return head.remove_next(data),
59 pub fn contains(&self, data: &T) -> bool {
60 if let Some(ref head) = self.head {
68 pub fn len(&self) -> usize {
69 if let Some(ref head) = self.head {
77 #[derive(Clone, Hash, Debug, PartialEq)]
78 struct Element<T: PartialEq> {
80 next: Option<Box<Element<T>>>,
83 impl<T: PartialEq> Element<T> {
85 fn remove_next(&mut self, data: &T) -> bool {
86 let new_next = if let Some(ref mut next) = self.next {
87 if next.data != *data {
88 return next.remove_next(data)
101 fn len(&self) -> usize {
102 if let Some(ref next) = self.next {
109 fn contains(&self, data: &T) -> bool {
110 if self.data == *data {
114 if let Some(ref next) = self.next {
129 fn test_contains_and_insert() {
130 fn do_insert(i : u32) -> bool {
134 let mut list = TinyList::new();
139 assert!(list.contains(&j));
141 assert!(!list.contains(&j));
145 assert!(!list.contains(&i));
149 assert!(list.contains(&i));
155 fn test_remove_first() {
156 let mut list = TinyList::new();
161 assert_eq!(list.len(), 4);
163 assert!(list.remove(&4));
164 assert!(!list.contains(&4));
166 assert_eq!(list.len(), 3);
167 assert!(list.contains(&1));
168 assert!(list.contains(&2));
169 assert!(list.contains(&3));
173 fn test_remove_last() {
174 let mut list = TinyList::new();
179 assert_eq!(list.len(), 4);
181 assert!(list.remove(&1));
182 assert!(!list.contains(&1));
184 assert_eq!(list.len(), 3);
185 assert!(list.contains(&2));
186 assert!(list.contains(&3));
187 assert!(list.contains(&4));
191 fn test_remove_middle() {
192 let mut list = TinyList::new();
197 assert_eq!(list.len(), 4);
199 assert!(list.remove(&2));
200 assert!(!list.contains(&2));
202 assert_eq!(list.len(), 3);
203 assert!(list.contains(&1));
204 assert!(list.contains(&3));
205 assert!(list.contains(&4));
209 fn test_remove_single() {
210 let mut list = TinyList::new();
212 assert_eq!(list.len(), 1);
214 assert!(list.remove(&1));
215 assert!(!list.contains(&1));
217 assert_eq!(list.len(), 0);
221 fn bench_insert_empty(b: &mut Bencher) {
223 let mut list = TinyList::new();
229 fn bench_insert_one(b: &mut Bencher) {
231 let mut list = TinyList::new_single(0);
237 fn bench_remove_empty(b: &mut Bencher) {
239 TinyList::new().remove(&1)
244 fn bench_remove_unknown(b: &mut Bencher) {
246 TinyList::new_single(0).remove(&1)
251 fn bench_remove_one(b: &mut Bencher) {
253 TinyList::new_single(1).remove(&1)