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>`.
18 pub struct TinyList<T: PartialEq> {
19 head: Option<Element<T>>,
22 impl<T: PartialEq> TinyList<T> {
24 pub fn new() -> TinyList<T> {
25 TinyList { head: None }
29 pub fn new_single(data: T) -> TinyList<T> {
30 TinyList { head: Some(Element { data, next: None }) }
34 pub fn insert(&mut self, data: T) {
35 self.head = Some(Element { data, next: self.head.take().map(Box::new) });
39 pub fn remove(&mut self, data: &T) -> bool {
40 self.head = match self.head {
41 Some(ref mut head) if head.data == *data => head.next.take().map(|x| *x),
42 Some(ref mut head) => return head.remove_next(data),
49 pub fn contains(&self, data: &T) -> bool {
50 let mut elem = self.head.as_ref();
51 while let Some(ref e) = elem {
55 elem = e.next.as_ref().map(|e| &**e);
61 pub fn len(&self) -> usize {
62 let (mut elem, mut count) = (self.head.as_ref(), 0);
63 while let Some(ref e) = elem {
65 elem = e.next.as_ref().map(|e| &**e);
72 struct Element<T: PartialEq> {
74 next: Option<Box<Element<T>>>,
77 impl<T: PartialEq> Element<T> {
78 fn remove_next(&mut self, data: &T) -> bool {
82 Some(ref mut next) if next.data == *data => {
83 n.next = next.next.take();
86 Some(ref mut next) => n = next,