Arrays (std::vector)

• All data in an array must be of the same type
  • Therefore, it is very fast, because we know the sizeof(obj), simply count memory address. Don’t need to sort every elements.
• Arrays have a fixed capacity
  • Arrays must store their data sequentially in memory.
  • The capacity of an array is the maximum number of elements that can be stored.
  • This only way to add another element is to allocate a new, larger array and copy over all of the data. (expensive!!)

Linked Memory

• A pointer called the “head pointer” stores the link to the beginning of the list
• A pointer to null ptr marks the end of the list

List::get

Should go through all elements before the index. (expensive!!)

List::insert

Easily expand the linked list.