9 things you didn’t know about static array data structures

Most arrays we encounter are dynamic arrays, the difference between a dynamic and a static array is that a dynamic array does not have a fixed size and a static array does.

Image for post
Image for post
  1. To look up an item by index in an array is constant time O(1). If you have the specific index of an object in an array, the computations to find that item in memory are all constant time as well.
  2. Adding an item to an array is constant time O(1). We always have a reference point to the last thing in a static array, so we can insert an item after the current end.
  3. In the worst case, inserting an item in an array is linear time O(n). When you insert into an array, all the items — starting at the index we are inserting into — have to be shifted one index. These items have to be “moved over” to make room for the new item being inserted. The worst-case scenario is when we insert at the 0th index, and every item in the array must shift over.
  4. In the worst case, deleting an item in an array is linear time O(n). For any item you delete (unless it is the last item), all of the items after that index have to be shifted over to fill the now blank spot in the array. Remember, arrays store data in sequential order, so if we delete an item, we cannot just leave that space blank. If we left the space blank, it would ruin the quick lookup time. To have the fast lookup time, we need to be able to rely on the distance from the start of the array to whatever index we are trying to access.
  5. The space complexity of an array is linear (O(n)). Each item in the array will take up space in memory.
  6. Static arrays are great because they allow fast lookups and fast appends. No matter how long the array is, getting an item from a specific index is a constant time (O(1)) operation. Adding a new element to the end of an array is a constant time operation O(1).
  7. The primary weakness of a static array is that it has a fixed size. You must have some knowledge about the size of the data you will be storing in advance because you need to specify the size of the static array when you create it.
  8. Another weakness is the linear time insertions and deletions. Every time you insert or delete an item from a position other than the end, other items in the static array have to be shifted over so that all of the data remains sequentially stored.
  9. The static array is a building block for many other data structures. The most notable is the dynamic array. A dynamic array allows you to use an array without specifying the array’s size when it is instantiated.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store