Continuing my look into language features, today I’m asking why are we still using arrays? Or more specifically why does Java have C-style arrays? An array is essentially a list, an ordered collection of things. Lists are a vital data structure in programming but why is there this first-class array primitive in Java?
Let’s first look at C. Arrays in C are nothing more than syntactical sugar for pointer arithmetic. Consider the following example.
int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
a[1]; /* equals 2 */
int *a = malloc(10 * sizeof(int));
for (int i = 0; i < 10; i++) {
*(a + i) = i;
}
*(a + 1); /* equals 2 */
These two bits of code are, for all intends and purposes, the same. Since they are the same there are some limitations placed on arrays in C, i.e. they are fixed length, and things need to be next to each other in memory because of the way pointer arithmetic works.
We don’t really want these restrictions on lists, I may want to change the number of elements, and where they’re located in memory should be an implementation detail. For the second point in particular, Java does make it an implementation detail when you decide to use ArrayList or LinkedList.
So what is an array in Java? It’s not an instance of the Array class, but it is an object. It has a field named ‘length’ (public final), and it implements the Cloneable interface. int[].class.getName() is [I. That doesn’t tell us much, but IMHO it’s a hack in the language to implement C-style arrays. It is fast, according to Peter Norvig’s IAQ on Java, accessing an array is 15-30 times faster than accessing an element of a Vector. But that could just be synchronization overhead, and Vector is probably implemented with arrays anyway. There should be some low level language feature that allows us to access that speed.
So what’s my gripe? Arrays in Java should be so much more than copies of the things in C. The Java Collections API which is one of the best Java APIs, and the List type should have the array syntax. Take a look at Arrays in Ruby, which are essentially a good list implementation with array syntax.
a = [1 ,2, 3, 4, 5]
a[1] » 2
b = [6, 7, 8, 9, 10]
a + b » [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
N.B. this produces a new array, but you can use the ‘concat’ method to append them to the same array
c = [2, 4, 6, 8, 10]
(a + b) - c » [1, 3, 5, 7, 9]
Ruby’s Array class also does a lot more.
The concept of C-style arrays need to be dropped. We don’t handle pointers any more, we shouldn’t be bound by the limitations. The concept we’re using is the list data structure, we should make that, along with all of its potential features, our first class type.
Update: I simplified the way to get the int[] class name (Thanks Shai).
Update 2: Corrected a typo in the C example (Thanks JDB).
Disclaimer: In the C example the first declaration will assign memory from the stack and the latter from the heap, so they’re not the same, but I just want to demonstrate elements in the array are next to each other in memory and hence [] notation can be changed to pointers.
Disclaimer 2: I know Vector’s methods are synchronized, and ArrayList is essentially the same thing without the synchronization overhead, hence faster. The performance numbers I pulled up are old and it used Vectors, thanks Shai for providing up to date numbers.