Arrays are another common way to store sequences of data. However, they lack a fundamental feature of lists: expansion. Arrays are efficient because they are a fixed-size container of length n, where every element has an equal size. Thus, any element can be reached by calculating the address to jump to using the simple formula start_address + n * element_size, making the entire process really fast. Additionally, this is very CPU cache-friendly, since the data is always at least one hop away.
The idea of using arrays to emulate list behavior has been around for a long time (Java 1.2 included an ArrayList class in 1998, but the idea is likely much older) and it is still a great way to achieve high performance in lists. Rust's Vec<T> uses the same technique. To start off, this is how an array list is built:
Consequently, this Rust implementation will have...
