IntoIter

Rust's iteration protocol is a single trait, Iterator, with one required method: fn next(&mut self) -> Option<Self::Item>. To iterate, you build a state-machine struct, implement Iterator for it, and yield items from next. There's no yield keyword; you write the state machine yourself.

1. 01
   There are three iter conventions in Rust, by the kind of access they grant: into_iter consumes the collection and yields owned values, iter borrows it shared and yields &T, iter_mut borrows it exclusively and yields &mut T. Standard collections all provide all three; we will too.

   // for x in &list      // calls list.iter()       -> &T
   // for x in &mut list  // calls list.iter_mut()   -> &mut T
   // for x in list       // calls list.into_iter()  -> T (consumes list)

2. 02
   IntoIter is the easiest of the three because we already wrote pop. Wrap the list in a tuple struct, and next is just self.0.pop(). The list shrinks as we go; when it's empty, pop returns None and the iterator naturally terminates.

   pub struct IntoIter<T>(List<T>);
   
   impl<T> List<T> {
       pub fn into_iter(self) -> IntoIter<T> {
           IntoIter(self)
       }
   }
   
   impl<T> Iterator for IntoIter<T> {
       type Item = T;
       fn next(&mut self) -> Option<T> {
           self.0.pop()
       }
   }

3. 03
   Now for x in list { ... } works. The for loop calls IntoIterator::into_iter, which we've effectively provided via the inherent method (the trait impl for for-loop interop is mechanical and we'll add it later). The list is moved into the iterator and dropped element by element.

   let mut list = List::new();
   list.push(1); list.push(2); list.push(3);
   let mut it = list.into_iter();
   assert_eq!(it.next(), Some(3));
   assert_eq!(it.next(), Some(2));
   assert_eq!(it.next(), Some(1));
   assert_eq!(it.next(), None);