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>`.
17 #[derive(Clone, Hash, Debug, PartialEq)]
18 pub struct TinyList<T: PartialEq> {
19 head: Option<Element<T>>
22 impl<T: PartialEq> TinyList<T> {
24 pub fn new() -> TinyList<T> {
31 pub fn new_single(data: T) -> TinyList<T> {
41 pub fn insert(&mut self, data: T) {
42 self.head = Some(Element {
44 next: self.head.take().map(Box::new)
49 pub fn remove(&mut self, data: &T) -> bool {
50 self.head = match self.head {
51 Some(ref mut head) if head.data == *data => {
52 head.next.take().map(|x| *x)
54 Some(ref mut head) => return head.remove_next(data),
61 pub fn contains(&self, data: &T) -> bool {
62 let mut elem = self.head.as_ref();
63 while let Some(ref e) = elem {
67 elem = e.next.as_ref().map(|e| &**e);
73 pub fn len(&self) -> usize {
74 let (mut elem, mut count) = (self.head.as_ref(), 0);
75 while let Some(ref e) = elem {
77 elem = e.next.as_ref().map(|e| &**e);
83 #[derive(Clone, Hash, Debug, PartialEq)]
84 struct Element<T: PartialEq> {
86 next: Option<Box<Element<T>>>,
89 impl<T: PartialEq> Element<T> {
90 fn remove_next(&mut self, data: &T) -> bool {
91 let new_next = match self.next {
92 Some(ref mut next) if next.data == *data => next.next.take(),
93 Some(ref mut next) => return next.remove_next(data),