>>Let's continue our study of arrays of primitive data by looking at allocation and access issues.
Here are the critical properties of arrays. All of the elements of an array must be of
the same type. Now this could be a primitive data type, something like int of double with
a little d. Or it could be references to a type of object. For example: references to
Strings. Array elements have to be placed into contiguous memory in the computer. This
is a very important limitation and is the cause of a lot of challenges we have working
with arrays. What's more, the number of elements must be known in advance and can't be changed.
The reason this is true is because the array elements have to be placed in contiguous memory.
So for example suppose we put elements in locations 100 to 105 and then we needed to
increase the size. There's no way for us to know that locations 106, 107, 108 haven't
been used for something else. So there's no way that we can make it bigger. This is a
real limitation.
Now there is a way to work around it, and that's you can construct a new array and then
copy everything over. But remember that's going to be expensive. While a lot of the
arrays that we've looked at in these examples are small, often three five elements mostly
so that I can draw them for you easily, arrays in the real world tend to be millions or even
billions of elements. Reallocating memory and copying things over gets to be very expensive.
So let's take a look at the mechanics of array allocation. Arrays are stored like objects.
Now what I mean by that is you create a reference and then you allocate them on the heap using
a constructor. Remember constructors always use the word new. So for example, int square
bracket data equals new int square bracket five. This is what this looks like in memory.
Data is a reference, and then we allocate five places on the heap. Now these five places
are going to hold integers. The arrow between data and the five places on the heap indicates
that the reference for data points to that location in memory. In other words the first
address is what's sitting in data.
As far as indexing arrays goes, well arrays are zero indexed. Now this should be expected
because you've seen this in array list Strings. Because array list and Strings contain arrays,
they're indexing is the same as arrays. This is actually kind of helpful because at least
everything works the same way. The reference list contains the address of the first element.
To get the address of other elements what you do is you add the address in the index.
Let's take a look at how this works.
So here we have data. Now the 372 that I'm showing in the data box is the reference to
the first element under the array. The number itself doesn't have any significance; it's
just an array address. And notice because they're in contiguous memory locations, the
second is at 373, the third is at 374, the fourth is at 375 and so on. So the way that
you get to the location in memory is you take 272, the address of the first element, and
then you add the index. So for example, the address 374 comes from adding two to 372.
This is actually why we zero index things-- it's so this little equation works. What it
does is it makes it possible to jump to any place in the array with just one addition
operation. That property is called random access, and it's critically important for
programming. Now arrays do have a data feel that gives the number of elements that have
been allocated. So if we do int square bracket data equals new int square bracket five, same
as we've been doing all along data dot length is going to be five. Now first off notice
this is unit indexed not zero indexed. What's more there are no parentheses. Now the reason
there are no parentheses here is because length isn't a method. It's data that's stored in
the array. This is kind of a weird operation, and don't get worried about making mistakes
like this on tests. I won't take off points for it because it's such a minor error-- but
it is kind of an important point. The other thing to remember is there is no data square
brackets of five. Now that seems really odd, but remember the five in this data of square
brackets that is the index. Well indices are zero indexed, whereas length is unit indexed.
This stuff drives you crazy at first but you do get used to it after a very short period
of time. Now Java does check to make sure you're not going over the end of the array.
This is a very nice thing for beginning programmers because one of the hardest mistakes to find
is stepping over the end of the array. If you do happen to do this accidentally, you'll
see an array index out of bounds exception. Let's look at some typical loop operations.
If we have our same array that we've been allocating all along, for int index equals
zero index less than data dot length plus plus index. Remember data dot length is the
number of elements in the array. Because it's unit indexed we want to use less than, not
less than or equal too. And then we can do whatever we want in the array. In this case
I've just done a system out print line for a data element. So that's a very typical for
loop. And it's really the most flexible and useful one. So the pattern you're seeing here
is you start with zero and you end with less than and the data dot length. That pattern
holds because of the differences between unit indexing and zero indexing. Here's another
option though. Now this one has sort of a strange name - it's called a for each loop.
So you do for int I colon data. So data's the name of the array, or to be more precise
it's the reference to the array. And we have int I because it's an array of integers. Now
when you do system out print line you can just use I instead of indices. So this isn't
stepping through indices, it's actually stepping through elements of the array. Now why this
is called a for each loop is mostly due to historical reasons. When this was first proposed
to be part of Java, people wanted it to be called for each to have a different name.
But people who implement Java decided it would be easier to do this with just the for. Unfortunately
the name stuck, so you'll just have to deal with the subtle difference. Now there is a
limitation to for each loops and that is you're only allowed to access the elements you're
not allowed to change them. So for example we can't do add or remove to the array inside
the loop.
So let's talk a little bit about how arrays and array lists are different. Now array list
objects do contain a hidden array. You can sort of guess that from the name. Primitive
data types however aren't allowed. Now this is hard to see, because Java does a little
trick with wrapper classes. So instead of putting an array of ints it puts an array
of integer, integer is the wrapper class that matches the primitive data type int. This
is concealed from you by a trick that's called auto boxing. It's a little beyond the scope
of the class so we're not going to worry about it too much. If you want to look into it a
search on auto boxing will give you lots of details. Array list objects resize the array
when you run out of space. Now you'll remember that I said arrays couldn't be resized-- that
is without reconstruction. So what the array list is really doing is reconstructing the
array and copying things over. Now these details are concealed from a naïve programmer and
this can be a hidden expense. In fact when my former students call me up and ask me for
help on a program, this particular problem is one that shows up a lot. So be aware of
the fact that the array list has this hidden expense, so it doesn't surprise you someday.
Keep programming!