Arrays

An array is a linear collection of data values that are accessible at numbered indices, starting at 0. Arrays are stored in continguous memory. There are two types of arrays, static and dynamic. Static arrays are fixed length, meaning they will always take up the same amount of memory.

Dynamic arrays can change in size, and in statically typed languages like C++ there are called vectors. Dynamic arrays allocate double the amount of memory you have specified to account for adding values to it. When you reach a full array, then it allocates a new array with double the size and copies the values over which is an O(n) operation.

Complexity

• Accessing at index: O(1)
• Updating at index: O(1)
• Inserting at beginning: O(n)
• Inserting in middle: O(n)
• Inserting at end: O(1) for dynamic, O(n) for static or reallocating dynamic
• Removing from beginning: O(n)
• Removing from middle: O(n)
• Removing from end: O(1)
• Copying: O(n)
• Traversing (including mapping, filtering, etc): O(n)