Sequences

The most-used dynamic sequence in Rust and in most languages is the vector, represented in Rust as Vec. You can add elements to the back of a vector with the push() method, and get the last element back with the pop() method. You can also iterate through the vector and, by default, it will go from front to back, but you can also reverse the iterator to go from back to front. In general, a vector in Rust can be compared to a stack, since it's primarily a LIFO structure.

Vectors are really useful when you want to add new elements to a list, and when you are fine with working with indexes in slices to get the elements. Remember that vectors can be referenced as slices, and can be indexed with ranges. An interesting thing is that you can convert a vector into a boxed slice, that is similar to an array, but allocated in heap instead of a stack. You only have to call the into_boxed_slice() method. This is useful when you have finished growing the vector and want it to occupy less RAM. A vector has a capacity, a length, and a pointer to the elements, while a boxed slice will only have the pointer and the length, avoiding some extra memory usage.

Another useful sequence is the VecDeque sequence. This structure is a FIFO queue, where you can append elements to the back of the queue using the push_back() method, and pop elements from the front by using pop_front(). This can be used as a buffer since it can be consumed from the front while you continue adding elements to the back. Of course, to use it as a buffer crossing thread boundaries, you will need to lock it with a Mutex, for example. Iterations in these queues go from front to back, the same way as in vectors. It's implemented with a growable ring buffer.

Finally, the LinkedList is another sequential list where its peculiarity is that instead of having a chunk of elements in the memory, each element gets linked to the one before and the one after so that there is no need for an index. It's easy to iterate, and easy to remove any element in the list without leaving gaps or having to reorder the memory, but in general, it's not very memory-friendly and requires more CPU consumption.

You will, most of the time, prefer a Vec or a VecDeque. LinkedLists are usually only a good option when many inserts and removes have to be done in the middle of the sequence, since in that case, Vecs and VecDeques will have to reorder themselves, which takes a lot of time. But if you will usually only change the structure of the list from the back, a Vec is the best option; if you will also change it from the front, a VecDeque. Remember that in both you can read any element easily by indexing, it's just that it's more time-consuming to remove or add them in the middle of the list.