Data Structures: Arrays

An array is a data structure with a fixed length. Each element of the data structure has an index, which is how we access them. For an array $A$ we denote $A[i]$ as the element at index $i$, where $0\le i<\text{length}(A)$.

We can create a new array in $O(n)$ and access array elements in $O(1)$. One practical downside to arrays is that they use a lot of memory: suppose you make an array of size $1000$ to keep track of some things in your program, but end up only storing $10$ elements in it; that other empty memory cannot be touched by anything else.