How to do it...

Iterators are typically their own structs and, since there can be different types (for example, for returning references instead of owned values), they are a good choice architecturally as well:

1. Let's create the struct for the iterator of List<T>:

pub struct ConsumingListIterator<T>
where
    T: Clone + Sized,
{
    list: List<T>,
}

impl<T> ConsumingListIterator<T>
where
    T: Clone + Sized,
{
    fn new(list: List<T>) -> ConsumingListIterator<T> {
        ConsumingListIterator { list: list }
    }
}

1. So far, this is only a regular struct that lacks everything an iterator should have. Their defining nature is a next() function that advances the internal pointer and returns the value that it just moved off of. In typical Rust fashion, the returned value is wrapped in an Option that becomes None once the collection runs out of items. Let's implement the Iterator trait to get all of these features:

impl<T> Iterator for ConsumingListIterator<T>
where
    T: Clone + Sized,
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.list.pop_front()
    }
}

1. Right now, we could instantiate ConsumingListIterator and pass our own List instance to it and it would work well. However, that is far from a seamless integration! The Rust standard library offers an additional trait to implement IntoIterator. By implementing this trait's functions, even a for loop knows what to do, and it looks just like any other collection and is easily interchangeable:

impl<T> IntoIterator for List<T>
where
    T: Clone + Sized,
{
    type Item = T;
    type IntoIter = ConsumingListIterator<Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        ConsumingListIterator::new(self)
    }
}

1. Lastly, we need to write a test to prove that everything is working. Let's add this to the existing test suite:

    fn new_list(n: usize, value: Option<usize>) -> List<usize>{
        let mut list = List::new_empty();
        for i in 1..=n {
            if let Some(v) = value {
                list.append(v);
            } else {
                list.append(i);
            }
        }
        return list;
    }

    #[test]
    fn test_list_iterator() {
        let list = new_list(4, None);
        assert_eq!(list.length, 4);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(4));
        assert_eq!(iter.next(), None);

        let list = new_list(4, Some(1));
        assert_eq!(list.length, 4);

        for item in list {
            assert_eq!(item, 1);
        } 

        let list = new_list(4, Some(1));
        assert_eq!(list.length, 4);
        assert_eq!(list.into_iter().fold(0, |s, e| s + e), 4);
    }

1. Running the tests will show how well this integration works. The cargo test command's output demonstrates this:

$ cargo test
    Finished dev [unoptimized + debuginfo] target(s) in 0.02s
     Running target/debug/deps/custom_iterators-77e564edad00bd16

running 7 tests
test tests::bench_list_append ... ok
test tests::test_list_append ... ok
test tests::test_list_new_empty ... ok
test tests::test_list_split ... ok
test tests::test_list_iterator ... ok
test tests::test_list_split_panics ... ok
test tests::test_list_pop_front ... ok

test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests custom-iterators

running 5 tests
test src/lib.rs - List (line 52) ... ignored
test src/lib.rs - List<T>::append (line 107) ... ok
test src/lib.rs - List<T>::new_empty (line 80) ... ok
test src/lib.rs - List<T>::pop_front (line 134) ... ok
test src/lib.rs - List<T>::split (line 173) ... ok

test result: ok. 4 passed; 0 failed; 1 ignored; 0 measured; 0 filtered out

The next section is going to dive deeper into what's happening behind the scenes!