Arrays and Dynamic Arrays
In the traditional definition of an array, the key concept is that elements of an array occupy a contiguous block of memory. This has a couple important consequences. First, once created, an array cannot grow (because the adjacent memory might already be taken). Secondly, arrays can be randomly accessed. When you use square brackets to access an array element [X]), you are actually saying move forward within the memory from the start of the allocation by X. That explains why indexes start at 0, because the first item is retrieved by moving forward by 0.
Many languages have, what they call, "arrays" that can grow. Technically, these are dynamic arrays. Java and C# have ArrayLists which are also dynamic arrays. A dynamic array wraps a real array and allows it to grow. How? Once the array fills up, a new, larger, memory location is found and the original is copied to the new space.
Implementation
function ArrayList(initialLength) {
this.length = 0;
this.array = new Array(initialLength);
this.add = function(value) {
if (this.length == this.array.length){
this.grow();
}
this.array[this.length++] = value;
};
this.grow = function() {
var original = this.array;
this.array = new Array(this.length * 2);
for(var i = 0; i < this.length; ++i) {
this.array[i] = original[i];
};
}
}
var array = new ArrayList(1);
array.add(2);
array.add(9);
array.add(4);
Example
Click step to add the values to our dynamic array
Characteristics
When an insert occurs in a filled dynamic array, the growth algorithm must be executed. This means that inserts provide inconsistent performance as well as non-linear growth. The implementation of the growth algorithm obviously has a great impact. Like our implementation, many simply double the size; however, most are able to provide more efficient copying than what we've done.
In The Real World
Strings are the most common example of fixed arrays we use. They truly should be considered arrays of characters. And, like all arrays, their size is set when initialized. This is why many people warn that string are immutable and that appending multiple times causes poor performance. Like a dynamic array, a string must be reallocated to a larger space whenever values are appended. However, unlike a dynamic array this is handled at compile time and no buffering is used. In other words, appending a value to a string will allocate just enough space for the new combined value. This is where StringBuilder classes come into play. A StringBuilder is nothing more than a dynamic arrays for strings with some extra buffer space. When it fills up, it too must be copied to a new, larger, memory block.
The most important thing to do, when dealing with a dynamic array which will see many inserts, is to specify an adequate initial size. Many implementations start with a small default, say 20. This means that if you are inserting 10 000 values, it'll have to grow 9 times. It'll also fragment your memory (leaving 8 empty holes), causing additional compaction.
Some languages, such as Ruby rely solely on dynamic arrays. Others, like Java and C# expose both types. In this day and age, it's hard to come up with real-world use cases for absolutely requiring fixed arrays.