Wrap up

A (transaction) log is a great use case for a linked list: They often grow to unexpected sizes, and indexing is not required. While a linked list is often a very simple type in other languages, it harbors a surprising amount of challenges in Rust. This is mostly due to the borrowing and ownership concepts which require a programmer to think about what goes where in great detail. For real-world use cases, however, it's better to use Rust's standard library linked list (std::collections::LinkedList). From a performance perspective, finding a particular item in the singly linked list requires looking at the entire list in the worst case, resulting in a runtime complexity of O(n), with n being the number of items in the list (more on the topic of runtime complexity in Chapter 8, Algorithm Evaluation).