Dynamic array

• Quick summary: an array that can resize itself.
• Also known as: array list, list, growable array, resizable array, mutable array, dynamic table.
• Important facts:
  • Same as array in most regards: stores elements sequentially, uses numeric indexing, allocates contiguous memory space.
  • Expands as you add more elements. Doesn't require setting initial capacity.
  • When it exhausts capacity, a dynamic array allocates a new contiguous memory space that is double the previous capacity, and copies all values to the new location.
  • Time complexity is the same as for a fixed array except for worst-case appends: when capacity needs to be doubled, append is O(n). However, the average append is still O(1).
• Pros:
  • Variable size. A dynamic array expands as needed.
  • Constant time access.
• Cons:
  • Slow worst-case appends: O(n). Average appends: O(1).
  • Insertion and deletion are still slow because subsequent elements must be moved a single index further. Worst-case (insertion into/deletion from the first index, a.k.a. prepending) for both is O(n).
• Time complexity (worst case):
  • Access: O(1)
  • Search: O(n)
  • Insertion: O(n) (append: O(n))
  • Deletion: O(n)
• See also: same as arrays (see above).