How do dynamic arrays work?

Static Arrays

One thing I disliked about C was that I had to know how many elements were going to be in an array at the time it’s initialized. For example, to make an array of 10 integers you would have to declare it as,

int arr[10];

Then you can put actual integers into it using something like a for loop (it initializes with garbage values in every index otherwise),

for (int i = 0; i < 10; i++) { 
  arr[i] = i;
}

That may seem like a small gripe, but when you start adding user interaction you need a way of handling arbitrary inputs. One solution is to allocate a gigantic amount of memory and just assume the user will get bored of your program before they hit the limit. Another solution is to allocate memory cleverly using malloc() and free(). Isn’t there a better (re: easier) way?

Dynamic Arrays 

One thing I really like about programming languages like Ruby, Python, and JavaScript is arrays are natively dynamic. That means if you declare a pointer to an array in ruby,

arr = []

You can push elements into that array to your heart’s content.

9999.times { |i| arr << i }

Ruby compiles down to C, though, so how come the arrays act different? Ruby arrays dynamically allocate memory based on need, so the programmer doesn’t have to worry about it. How does Ruby accomplish this without allocating a massive amount of memory for every array?

Arrays are initialized as a fixed size, but under certain circumstances they perform an O(n) operation to double the size of the array. Every time this operation occurs, we now have twice as much data we can put in the array. Therefore, push operations still only take O(1) amortized time. You may suspect that in order to add elements to the start of the array it should take O(n) time because we have to scoot every value over, but unshift also only takes O(1) time. This is achieved because the array’s data store acts like a Circular Buffer and adding elements to the beginning or the end of the array is equally as efficient.

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *