Logout

--- Abstract data structures ---

5.1.4

Describe the characteristics of a two-dimensional array.

Teaching Note:

LINK One-dimensional arrays and basic algorithms.

Sample Question:

sdfsdfsf

JSR Notes:

### Important set-up and context of these notes

Since this is now HL material, with these notes, we are first going to go back and take a much more in-depth look at arrays in general. We will do that here in 5.1.4. Then, in 5.1.5 we will focus in on 2D arrays.

But in terms of this assessment statement in and of itself, the main thing in the description is as follows:

### Characteristics of 2D Arrays

The main characteristic of a 2d array is that it stores an array of arrays; i.e. each element in an array is itself a multiple item array. So in the example of a table, there are multiple rows, but each rows is itself an array (an array of column elements).

****Now back to Arrays in general, but to a deeper level than Topic 4****

### Arrays Data Types vs. Data Structures

Before we diverged into the nature of objects, we had been looking at Java primitive data types such as ints, booleans, and doubles. Now we look at our first data structure, the array. To get straight the difference between a primitive data type, an object, and a data structure, consider the following definitions.

primitive data type - a certain type of data defined not only by how it is used (for example, as a character versus as a real number), but also on how much memory it occupies (a 16 bit char versus a 64 bit double). Examples: long, float, char.

object - a reference to a specific instance of a certain class made up of certain data and methods that act on that data. Examples: BufferedReader br, TicketingAccount t, System.in.

data structure - a group of similar data or objects organized somehow. Examples: arrays, linked lists, binary search trees (all of which we cover in the course.)

As with all definitions, they will only be perfectly clear after having gained experience "on the ground" with them.

### Arrays

So, our first data structure we look at is arrays. The rationale for the placement of arrays here is that it follows on nicely from looking at primitives, and also, before getting into loops as a method to manage flow of control, it makes sense to get the idea of arrays straight.

In fact, we have seen arrays several times, right from day 1 when we used the args array found as an argument of all main methods:

public static void main(String [] args)

You can think of an array as a container. It is a container that stores many things all of the same type. (In some programming languages you can have arrays which contain elements of various types, but not in Java.) So a simple analogy would be a carton of eggs. The carton itself is the array, the eggs are what make up the content of the carton. The individual pieces of content within the array are most properly called as "elements". So a carton of eggs is an array, with 12 egg elements. Each egg would be identified by its number, starting with 0; so egg-0, egg-1, egg-2, and so on, up to egg-12.

-------------------------------------------------------------------------------------------------------------------

### Declaring Arrays

Here is how we declare an array: (We could use any type, but for the example we'll use int)

int [] myIntArray = new int [5];
(The way you shold read the above declaration is "int array myIntArray is asssigned a new int array of size five".)

What this does is finds a place in memory where there is 5 x 32 bits available (that would be a total of 160 available bytes). And that block of available memory would be referred to as "myIntArray" until the array was garbage collected.

Note that the whole way arrays work, in terms of being able to find elements of them is that all the elements are next to each other. The term we use to describe this is "contiguous". We say that the elements of an array are all located next to each other in a contiguous part of RAM memory big enough to accomodate them.

(and who knows what values are actually lingering in those 160 bytes...)

-------------------------------------------------------------------------------------------------------------------

### Initializing Arrays

***It is very important at this point to realize that only default values have been assigned to each element of the array; in the case of ints, they are initialized to 0. And though this isn't such a big deal, later on in the course when we are making arrays of our own objects, this will be a big deal. So it's a good habit to get into to initialize all elements ourselves, immediately after declaring an array. So:

int [] myIntArray = new int[5];
myIntArray[0] = -999;
myIntArray[1] = -999;
myIntArray[2] = -999;
myIntArray[3] = -999;
myIntArray[4] = -999;

So, above, the 0th element of the array is assigned the value -999, and the "1st" element of the array is assigned -999, and so on. Do note that with 0 numbering, the elements are numbered 0 to 11, and the length, done with traditional numbering, is 12. This can cause confusion and errors, so try to remember this from the start.

(The one thing that you may wonder is if there is a way to not have to copy and paste so much; it's not too bad if there are only 12 elements, but what if there were 12,000,000. And, yes, there is a way, with looping structures that we will look at later on.)

Then, as a program actually uses the array, the values will take on more meaningful, non-default, values. Let's say, for example, this was from a program that kept a person's five favorite integers. (how 'bout that for a lame example...)

System.out.println("What is your most favourite integer?)
System.out.println("What is your second most favourite integer?)
etc.

-------------------------------------------------------------------------------------------------------------------

### Here's an actual full Java example

(though at this point it won't be able to be too useful)

``` 1 import java.io.*;
2
3 public class ForArraysNotes {
4     public static void main(String[] args) {
5         try{
6             int [] gradesArray = new int[3];
13             System.out.println("What is the grade you got in Writing?");
15             System.out.println("What is the grade you got in Arithetic?");
17
19             System.out.println("The average grade you got in \"The Three 'R's\"" + " was " + averageGrade);
20         }
21         catch(Exception e){
22             System.out.println(e.getMessage());
23         }
24     }
25 }
```

The output for this would be:

90
What is the grade you got in Writing?
80
What is the grade you got in Arithmetic?
100
The average grade you got in "The Three R's" was 90

-------------------------------------------------------------------------------------------------------------------

### How Elements of An Array Are Located

You really don't have to know this point, but appreciating it now will help you later on, since data stored permanently in files works based on the same concept. So the idea is that the computer knows fundamental three things about the array: how big it is, the data type that it is made of, and the address of where the array starts. So to find any particular element of the array in memory, it simply takes the starting address, and adds on the following number of bits: the element number multiplied by the number of bits of the data type being held.

So if an integer array called intArr started at the hexadecimal address AAAA0000, the second element of it (i.e. intArr[2]) would start exactly 64 bits (2 x 32) on from AAAA0000, which in hexadecimal is address AAAA0040. (By the way, that's becasue the second numeric place in hexadecimal is the 16 ^ 1 place, or the 16s, and 4 groups of 16 is 64 - more on this later on in the course.)

-------------------------------------------------------------------------------------------------------------------

### Index Out of Bounds Error

One thing to note now, and it will come into play often in the future, is to make sure you are trying to access an array element that actually exists. For starters, there could never be an element named with a negative sign. So, for example, in the above program, gradesArray[-2] does not exist. But neither does gradesArray[3]. This is a very common error, in which you are trying to access the last element of the array, and you forget that arrays are numbered starting at 0.

Trying to access an array element that does not exist is only caught when running the program - no red squigglies will appear while you are coding. An error that is picked up only when a program is run is called a "runtime error". And this particular kind of runtime error is called "index out of bounds error".

-------------------------------------------------------------------------------------------------------------------

### Alternative Way of Declaring an Array

An array can be declared and initialized all in one line using braces, like as follows:

int[] myOtherIntArray = {2, 4, 23, 343, 8978};

You'll note that when it is done this way, there is no need to declare the number of elements, because it's already obvious.
And note that we would still access the elments of the array the same way, so, for example, myOtherIntArray[3] is 343.

Also note in the diagram below that the myOtherIntArray points directly to where the array begins, rather than to a 32 bit address storing where the array begins - as happens above with using the new operator. Though in using both arrays, there's practically no difference.

There Are Actually Two Ways to Name Arrays The Braces Way

(This is just here for a sense of completion - you don't really need to be aware of this for IB CS, but looking in other places like on the Internet, you may come across this.)

There are two ways to declare arrays; the name and the [] brackets can be switched around. Both of the following are syntactically correct:

int [] myIntArray = new int[10]

and

int myIntArray [] = new int[10];

Personally, I prefer the first, since it reads better left to right: "int array myIntArray is assigned a new int array of ten elements."

And remember that you can always do it the explicit way like: int [] myIntArray = {1, 32, 34, 234, 234, 778, 887, 213, 3443, 12};

-------------------------------------------------------------------------------------------------------------------

### The Length Attribute of Arrays

All arrays have a length attribute, which can be accessed using dot notation. So from the above example, if we went:

System.out.println("The length of the array is " + myOtherIntAray.length);

we would get as output:

The length of the array is 5

***Note that the following line of code will always yeild an index out of bounds error (as discussed above), since the length attribute uses conventional numbering starting at 1, and the elements of an array are numbered using traditional computer numbering starting with 0:

System.out.printn(myOtherArray[length]); // INDEX OUT OF BOUNDS ERROR.

Whereas this line would be fine:

System.out.println(myOtherArray[length - 1]);