编写一个使用元素(Elements)和列表(List)的简单链表实现.

链表是计算机科学中的一种基本数据结构，常用于其他数据结构的实现。它们在函数式编程语言(如 Clojure、Erlang 或 Haskell)中很普遍，但是在命令式语言(如 Ruby 或 Python)中很少见。

最简单的链表是单链表。列表中的每个元素，包含数据和一个”next”字段，指向元素列表中的下一个元素。

链接列表的这种变体通常用于表示序列，或推/取堆栈(也称为 LIFO 堆栈;后进先出)。

作为第一步,让我们创建一个包含范围(1..10)的单一链接列表,并提供反转链接列表，和转换为数组，或从数组转换的函数.

在使用内置链表的语言实现这一点时,实现自己的抽象数据类型.

不要实现结构SimpleLinkedList作为一个Vec包装。 你应该,在堆上分配节点。 这可以实现为:

# #![allow(unused_variables)]
#fn main() {
pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
}
#}

这个head字段指向该链表的第一个元素(节点)。 这个实现也需要一个Node结构，其具有以下字段:

# #![allow(unused_variables)]
#fn main() {
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}
#}

data包含存储的数据,以及next指向下节点(如果可用)或无.

自己试试.您将得到以下错误.

| struct Node<T>
| ^^^^^^^^^^^^^^ recursive type has infinite size
...
| next: Option<Node<T>>,
| --------------------- recursive without indirection

这个错误在于,编译时,rust 必须知道下一个节点的大小。因next会是递归的(”一个节点，有一个节点-有一个节点…”)，编译器不知道要分配多少内存。相反,Box是一个具有定义大小的堆指针.

受”Ruby”中面向对象设计模式的数据结构和算法的启发,即单链表.http://www.brpreiss.com/books/opus8/html/page96.html#SECTION004300000000000000000

pub struct SimpleLinkedList<T> {
   // Delete this field
   // dummy is needed to avoid unused parameter error during compilation
   dummy: ::std::marker::PhantomData<T>,
}

impl<T> SimpleLinkedList<T> {
   pub fn new() -> Self {
       unimplemented!()
   }

   pub fn len(&self) -> usize {
       unimplemented!()
   }

   pub fn push(&mut self, _element: T) {
       unimplemented!()
   }

   pub fn pop(&mut self) -> Option<T> {
       unimplemented!()
   }

   pub fn peek(&self) -> Option<&T> {
       unimplemented!()
   }
}

impl<T: Clone> SimpleLinkedList<T> {
   pub fn rev(&self) -> SimpleLinkedList<T> {
       unimplemented!()
   }
}

impl<'a, T: Clone> From<&'a [T]> for SimpleLinkedList<T> {
   fn from(_item: &[T]) -> Self {
       unimplemented!()
   }
}

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
   fn into(self) -> Vec<T> {
       unimplemented!()
   }
}

# #![allow(unused_variables)]
#fn main() {
#[test]
fn test_new_list_is_empty() {
   let list: SimpleLinkedList<u32> = SimpleLinkedList::new();
   assert_eq!(list.len(), 0, "list's length must be 0");
}

#[test]
//#[ignore]
fn test_push_increments_length() {
   let mut list: SimpleLinkedList<u32> = SimpleLinkedList::new();
   list.push(1);
   assert_eq!(list.len(), 1, "list's length must be 1");
   list.push(2);
   assert_eq!(list.len(), 2, "list's length must be 2");
}

#[test]
//#[ignore]
fn test_pop_decrements_length() {
   let mut list: SimpleLinkedList<u32> = SimpleLinkedList::new();
   list.push(1);
   list.push(2);
   list.pop();
   assert_eq!(list.len(), 1, "list's length must be 1");
   list.pop();
   assert_eq!(list.len(), 0, "list's length must be 0");
}

#[test]
//#[ignore]
fn test_pop_returns_last_added_element() {
   let mut list: SimpleLinkedList<u32> = SimpleLinkedList::new();
   list.push(1);
   list.push(2);
   assert_eq!(list.pop(), Some(2), "Element must be 2");
   assert_eq!(list.pop(), Some(1), "Element must be 1");
   assert_eq!(list.pop(), None, "No element should be contained in list");
}

#[test]
//#[ignore]
fn test_peek_returns_head_element() {
   let mut list: SimpleLinkedList<u32> = SimpleLinkedList::new();
   assert_eq!(list.peek(), None, "No element should be contained in list");
   list.push(2);
   assert_eq!(list.peek(), Some(&2), "Element must be 2");
   assert_eq!(list.peek(), Some(&2), "Element must be still 2");
}

#[test]
//#[ignore]
fn test_from_slice() {
   let array = ["1", "2", "3", "4"];
   let mut list = SimpleLinkedList::from(array.as_ref());
   assert_eq!(list.pop(), Some("4"));
   assert_eq!(list.pop(), Some("3"));
   assert_eq!(list.pop(), Some("2"));
   assert_eq!(list.pop(), Some("1"));
}

#[test]
//#[ignore]
fn test_reverse() {
   let mut list: SimpleLinkedList<u32> = SimpleLinkedList::new();
   list.push(1);
   list.push(2);
   list.push(3);
   let mut rev_list = list.rev();
   assert_eq!(rev_list.pop(), Some(1));
   assert_eq!(rev_list.pop(), Some(2));
   assert_eq!(rev_list.pop(), Some(3));
   assert_eq!(rev_list.pop(), None);
}

#[test]
//#[ignore]
fn test_into_vector() {
   let mut v = Vec::new();
   let mut s = SimpleLinkedList::new();
   for i in 1..4 {
       v.push(i);
       s.push(i);
   }
   let s_as_vec: Vec<i32> = s.into();
   assert_eq!(v, s_as_vec);
}

#}

# #![allow(unused_variables)]
#fn main() {
pub struct SimpleLinkedList<T> {
   head: Option<Box<Node<T>>>,
   len: usize,
}

struct Node<T> {
   data: T,
   next: Option<Box<Node<T>>>,
}

impl<T> SimpleLinkedList<T> {
   pub fn new() -> Self {
       SimpleLinkedList { head: None, len: 0 }
   }

   pub fn len(&self) -> usize {
       self.len
   }

   pub fn push(&mut self, element: T) {
       let node = Box::new(Node::new(element, self.head.take()));
       self.head = Some(node);
       self.len += 1;
   }

   pub fn pop(&mut self) -> Option<T> {
       match self.len {
           0 => None,
           _ => {
               self.len -= 1;
               self.head.take().map(|node| {
                   let node = *node;
                   self.head = node.next;
                   node.data
               })
           }
       }
   }

   pub fn peek(&self) -> Option<&T> {
       self.head.as_ref().map(|node| &node.data)
   }
}

impl<T: Clone> SimpleLinkedList<T> {
   pub fn rev(&self) -> SimpleLinkedList<T> {
       let mut rev_list = SimpleLinkedList::new();
       let mut next = self.head.as_ref().map(|node| &**node);
       while let Some(node) = next {
           rev_list.push(node.data.clone());
           next = node.next.as_ref().map(|node| &**node);
       }
       rev_list
   }
}

impl<'a, T: Clone> From<&'a [T]> for SimpleLinkedList<T> {
   fn from(item: &[T]) -> Self {
       let mut list = SimpleLinkedList::new();
       for i in item {
           list.push(i.clone());
       }
       list
   }
}

impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
   fn into(mut self) -> Vec<T> {
       let mut vec = Vec::new();
       while let Some(data) = self.pop() {
           vec.push(data);
       }
       vec.reverse();
       vec
   }
}

impl<T> Node<T> {
   pub fn new(element: T, next: Option<Box<Node<T>>>) -> Self {
       Node {
           data: element,
           next,
       }
   }
}

#}