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> {
25 pub fn new() -> TinyList<T> {
32 pub fn new_single(data: T) -> TinyList<T> {
42 pub fn insert(&mut self, data: T) {
43 self.head = Some(Element {
45 next: self.head.take().map(Box::new)
50 pub fn remove(&mut self, data: &T) -> bool {
51 self.head = match self.head {
52 Some(ref mut head) if head.data == *data => {
53 head.next.take().map(|x| *x)
55 Some(ref mut head) => return head.remove_next(data),
62 pub fn contains(&self, data: &T) -> bool {
63 if let Some(ref head) = self.head {
71 pub fn len(&self) -> usize {
72 if let Some(ref head) = self.head {
80 #[derive(Clone, Hash, Debug, PartialEq)]
81 struct Element<T: PartialEq> {
83 next: Option<Box<Element<T>>>,
86 impl<T: PartialEq> Element<T> {
88 fn remove_next(&mut self, data: &T) -> bool {
89 let new_next = if let Some(ref mut next) = self.next {
90 if next.data != *data {
91 return next.remove_next(data)
104 fn len(&self) -> usize {
105 if let Some(ref next) = self.next {
112 fn contains(&self, data: &T) -> bool {
113 if self.data == *data {
117 if let Some(ref next) = self.next {