The Difference Between Static and Dynamic Arrays
Introduction
If you’ve never learned a low level programming language before you may have never noticed that there are two types of arrays. For example, in JavaScript arrays are dynamic by default, but in a language like C++ you have access to both types. In this blog I am going to go over the difference between both types of arrays, as well as give a rundown on their performance differences.
Static Arrays
When you allocate an array in a low-level language like C++ or Java, you have to specify upfront how many indices you want your array to have like so:
This makes the array static because it only has five indices that you can use. This makes it impossible to append items when all five indices are filled with values. The upside to this is that if you know that you are only going to have five elements, then appending to this array becomes worst case O(1) time. This is because the memory address is already there in your RAM, all you are doing is filling it with a value. Here is a quick reference for the big O of static arrays:
Static Array Big O
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Space: O(n)
Lookup: O(1)
Append: O(1)
Insert: O(n)
Delete: O(n)
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Dynamic Arrays
Dynamic arrays differ from static arrays in that they don’t have a fixed size. However, this is at the cost of having quick appends. How a dynamic array works is that it resizes itself whenever it runs out of space. This is usually by doubling itself. For example, if its size defaulted to 10 indices then it would double to 20. Let’s take a closer look at how it does this:
- When you allocate a dynamic array your language of choice will make a static array with a set size. Let’s say that this size is 10.
- Let’s say you go to append an 11th item to your array. This will make your array run out of space causing it to create a bigger array that’s double its size (20).
- After this the old array of size 10 needs to copy all of its values over to the bigger array that has a size of 20.
- Now the old array will tell your OS to delete it making that memory free memory.
- Finally, the bigger array of size 20 will now append your 11th item to it.
As you can see this is a very costly process, but it doesn’t always occur every time you append to it. For example, if my set size was 10 and I appended a 9th item, we would not go through this process. However, we always look at the worst case scenario and that means that appending to dynamic arrays is O(n) time. This is obviously worse than a static array, but we lose the restrictiveness of static arrays. Here is a quick reference for the big O of dynamic arrays:
Dynamic Array Big O
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Space: O(n)
Lookup: O(1)
Append: O(n)
Insert: O(n)
Delete: O(n)
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Conclusion
And that’s the difference between static and dynamic arrays! I hope you now understand the reason why we have both, and the negatives and positives of using each type. Thanks for reading!
Sources:
