Vectors versus lists
Prepending an element to a linked list is very fast. In fact, it is an O(1) operation, meaning the original list is simply pointed at by the new element node. The change happens only at the head of the list. As we don't need to traverse the list at all, this is a fixed cost, that is, O(1) operation.
Accessing an element at some index n is slower, meaning it is proportional to the number of elements in the list. We need to start at the head and keep traversing the nodes and keep counting. We do this until we reach the nth node. If we access the second last node, we will have traversed almost all of the list.
When any operation could make us look at almost all the elements, the complexity would be O(n). This means it would be proportional to the number of elements.
On the other hand, appending an element to a list is costly when we need to preserve the original list. In the next chapter, we need to traverse and copy all the elements, so we will preserve the current...
