Arrays

Suppose we want to write a program that computes the average midterm score of all the students and find out how many scored above the average. How many variables do we need for storing the scores? If we have 30 students in the class, then we would need at least 30 variables, right? Rather than declaring 30 variables, one by one, we can use a special data structure called an "array" to declare them all at once and work with them in a way that minimizes confusion.

An array is a data structure that represents an organized collection variables of the same type.

One-dimensional arrays can be thought of as a list of n variables numbered 0 through (n-1). (Note: computer scientists and mathematicians, unlike the rest of the people on the planet, always start counting with zero -- weird huh?!)

Two-dimensional arrays frequently (but not always) behave like a n × m table of variables. Technically, they are just one-dimensional arrays whose variables are themselves one-dimensional arrays. We'll talk more about these in a bit -- but first...

Higher dimensional arrays can be created as well, being just arrays of arrays of arrays of... (and so on).

Declaring and Creating Arrays

To declare a one-dimensional array, we can use the syntax seen in either of the following, although the first is preferred:

Syntax:

datatype[] arrayRefVar;    //This is the preferred way!

datatype   arrayRefVar[];  //Although Java won't complain if you
                           //declare arrays like this

Examples:

double[]  myFirstList;
int       mySecondList[];

The number of variables in your array determines the amount of memory that must be allocated to store that array -- and notice, the declaration doesn't say how big the array should be. So we have an additional step we must do before we can actually use the array -- we must tell the computer how many variables we wish to have in the array. This is called "creating" the array, and the syntax and an example are shown below:

Syntax:

arrayRefVar = new datatype[arraySize];

Example:

myList = new double[10];

We can declare and create an array in one step if we wish:

datatype[] arrayRefVar = new datatype[arraySize];

does the same thing as...

datatype[] arrayRefVar;
arrayRefVar = new datatype[arraySize];

Example:

double[] myList = new double[10];  //declares and creates
                                   //an array of 10 doubles

When an array is created, its elements are assigned a default value that depends on the type of the elements contained in the array.

  • 0 for the numeric primitive data types
  • (char) 0 for the char types
  • false for boolean types
  • null for reference types

Assigning Values to Array Elements

The ith element in a one-dimensional array named myList can be referenced by myList[i].

As such, if we wished to declare and create an array that would contain 10 doubles and then assign values to some of the elements in such an array, it might look like this:

double[] myList = new double[10];  //<--declaration and creation

myList[0] = 5.6;     //<--first element of the array
myList[1] = 4.5;     //<--second element of the array
myList[2] = 3.3;
myList[3] = 13.2;
myList[4] = 4;
myList[5] = 34.33;
myList[6] = 34;
myList[7] = 45.45;
myList[8] = 99.993;
myList[9] = 11123;   //<--last element of this array

//(Recall a list of 10 elements is indexed by 0 through 9, 
// so we've assigned values to all of the elements of this list)

There is a one-statement, shorthand syntax that we can use to accomplish the exact same thing as what is above:

double[] myList = {5.6, 4.5, 3.3, 13.2, 4, 34.33, 34, 45.45, 99.993, 11123};

The Length of an Array

Once an array is created, its size is fixed. It cannot be changed.

You can find the size of an array using the length instance variable:

Example:

int[] myNumbers = new int[10];
int len = myNumbers.length;
System.out.println(len);     //prints "10"

Be careful that you don't try to do something with an element of an array that doesn't exist. The position of an element in a one-dimensional array is called its index, and the only allowable indices for a one-dimensional array go from 0 to array.length-1. (Forgetting this fact is a frequent source of errors for folks just learning to program.)

Example:

double[] myList = new double[10];
myList[0] = 5.6;      //first element is assigned the value 5.6
myList[1] = 4.5;      //second element is assigned the value of 4.5
myList[10] = 3.33;    //<--ArrayIndexOutOfBoundsException

Using Array Elements

Once the elements of an array have been assigned values, they work just like any other value that has been assigned a value. We can combine them with other variables or with each other, we can reassign their values, we can print them (if the type can be printed), etc...

Example:

int[] tmpA = {7,8,6,3,23};
int myNum;
 
myNum = tmpA[4] - tmpA[0] * tmpA[3]; 

                //myNum is now 23-7*3 or 2


tmpA [tmpA[0]-5] = tmpA[myNum+1] + tmpA[1]; 

                //tmpA[myNum+1] is tmpA[3] which equals 3
                //tmpA[1] equals 8
                //tmpA[0] is 7
                //so we are assigning tmpA[2] the value 3+8
                //hence, tmpA now looks like {7,8,11,3,23}


System.out.println("tmpA[2] = " + tmpA[2]);  

                //prints "tmpA[2] = 11" to the screen

Using Loops to Make Tasks Involving Arrays Easier

Provided that we know the size of an array, we can use for-loops to quickly "process" all of the elements of the array. Here, the word "process" could indicate some common action (or inspection) that we wish to do to each element.

For example, if we wanted to print all of the elements of an array of integers that was previously declared, created, and assigned values, we might do the following:

for (int i=0; i < myArray.length; i++) {
   System.out.println(myArray[i]);
}

If we don't care about knowing the value of the index at each step through such a loop, but instead only need to know the values stored in the array (in order), we can use the enhanced for-loop (also called a for-each loop) syntax, which the below example illustrates:

for (int value: myArray)       //read "for each 'value' in 'myArray'"
   System.out.println(value); 

This would have the same result as the previous code, and is somewhat shorter -- although, as mentioned before, this comes with some limitations. Specifically, we give up knowledge of the corresponding index at each step through the loop, (which, by the way, means we can't change the values stored in the array inside such loops, as such assignments require the index of the element to be changed be specified).

We can also use loops to initialize the values of the elements in an array. For example, suppose we wanted to create an array of 10 doubles that was filled with random values from 0 to 100 (instead of the zeros we normally get by default) and then print those values to the screen. The following code would do just that:

double[] myList = new double[10];

for (int i=0; i < myList.length; i++) {
    myList[i] = Math.random() * 100;
}

for (double value: myList)
    System.out.println(value);

    //Prints something similar to the following:
    // 12.540623713370492
    // 90.39006993044325
    // 52.89191224241723
    // 6.982491326358398
    // 99.72365816092316
    // 99.64573590211609
    // 24.154783740132736
    // 84.50604842038284
    // 20.786482743884825
    // 78.95179899792404

Indeed, there are many uses for loops in conjunction with arrays. Here are some of the more common ones:

  • Initializing array elements
  • Printing arrays
  • Summing or averaging all of the elements in an array
  • Finding the largest (or smallest) element
  • Finding the smallest (or largest) index of the largest (or smallest) element
  • Shifting elements
  • Flipping elements
  • Counting occurrences of a particular value

Simple Array Algorithms

The following suggests possible implementations of several of the common array tasks previously mentioned:

Counting the Number of Occurrences of a Given Value

Algorithm:

  1. Initialize a counter to zero
  2. Loop through the elements of the array, increasing the counter by one each time there is a match

Example Code:

int count = 0;
for (int i=0; i < myList.length; i++) {
   if (myList[i] == 1)
      count++;

System.out.println("There were " + count + " occurrences of 1 in myList");
}

Finding a Maximum Value in an Array

Algorithm:

  1. Create a variable to store the current greatest value seen, initializing it with the first element of the array.
  2. Loop through the remaining elements of the array, and for each element examined, check to see if it is bigger than the one currently stored. If it is, update the one stored.

Example Code:

int max = myList[0];
for (int i=1; i < myList.length; i++) {
    if (max < myList[i])
        max = myList[i];
}
System.out.println("The maximum value in myList is " + max);

Example Code (using a for-each loop):

int max = myList[0];
for (int value: myList) {
    if (max < value) 
        max = value;
}

Finding the Smallest Index of the Largest Item

Algorithm:

  1. Initialize a variable that will store the current greatest value seen with the value of the first element of the array.
  2. Initialize a variable that will store the index of the current greatest value seen with 0
  3. Loop through the elements of the array. If a larger element is found, update both of the aforementioned variables

Example Code:

int max = myList[0];
int indexOfMax = 0;
for (int i=1; i < myList.length; i++) {
   if (myList[i] > max) {
      max = myList[i];
      indexOfMax = i;
   }
}

(What happens if we use myList[i] >= max ?)

Computing the Sum of All Elements in an Array

Algorithm:

  1. Initialize a variable that will store the sum thus-far with 0
  2. Loop through the elements of the array, adding each element to the sum stored.

Example Code:

int sum = 0;
for (int i=0; i < myList.length; i++) {
   sum += myList[i];
}

Example Code (using a for-each loop):

int sum = 0;
for (int value: myList) {
   sum += value;
}

Array References

When you declare and create an array, the variable used doesn't hold all of the information of the array -- instead, it holds a reference to where the information in the array is stored. You can think of it as a memory address. While this makes working with arrays more efficient in many ways, it does have some consequences:

Copying Arrays

One of the consequences of using a reference variable for arrays is that copying the contents of one array to another array doesn't work the same way as it does for primitive data types.

Consider the following code:

int originalNum;
int copyOfNum;

numA = 13;
numB = numA;          //numB now equals 13
numB = 7;             //now numB equals 7, 
                      //but numA still equals 13

System.out.println(numA);  //prints "13", as expected

But if you try to do something similar for arrays, something different happens:

int[] arrayA = new int[4];   //arrayA is initially {0,0,0,0}
int[] arrayB = new int[4];   //arrayB is initially {0,0,0,0}

arrayA[0] = 13;             //arrayA is now {13,0,0,0} 

arrayB = arrayA;             //this makes arrayB reference 
                             //the same information as arrayA 
                             //does. So now both arrayB and arrayA 
                             //reference a single array that looks
                             //like {13,0,0,0} and the array
                             //that used to be referenced by 
                             //arrayB still looks like
                             //{0,0,0,0}, but has no referencing
                             //variable and thus is "lost data" (garbage)

arrayB[0] = 7;              //Note, trying to change the contents of
                             //arrayB changes the contents of the array
                             //it references (which is the same as arrayA) 

System.out.println(arrayA[0]);    //Thus, this prints a "7" 
                                   //(and not "13")

Here's a graphical representation of what happened when made the assignment arrayB = arrayA;

If one really wants to make a duplicate copy of an array (instead of just two different variables that reference the same array), there are two nice ways to do it:

One way uses a for-loop to copy the elements of "source" array into an new "target" array:

int[] sourceArray = {2, 3, 1, 5, 10};
int[] targetArray = new int[sourceArray.length];

for (int i=0; i < sourceArrays.length; i++)
   targetArray[i] = sourceArray[i];

Another way uses the arraycopy method in the System class. This method is flexible in that it can copy an array (or subset of an array, of a given length) from the specified source array, beginning at the specified position (index), to the specified position (index) of the destination array.

Here's the syntax for a call to this method:

System.arraycopy(sourceArray, src_pos, targetArray, tar_pos, length);

And here's an example which copies everything from the source array to the target array:

System.arraycopy(sourceArray, 0, targetArray, 0, sourceArray.length);

Passing Arrays to Methods

Suppose you want to write a method that will print the contents of an array of integers. We can pass the array reference variable to the method just like any other variable:

public static void printArray(int[] array) {
   for (int i=0; i < array.length; i++) {
       System.out.print(array[i] + " ");
   }
}

public static void main(String[] args) {
   int[] list = {3, 1, 2, 6, 4, 2};
   printArray(list);
}

We do however need to understand what "pass by value" implies in this context.

For primitive types, like double, this means that the value of the variable is copied and the copy is given to the method to manipulate (i.e., the method parameter). Thus the method can't affect the value of the original variable passed to it.

However, for a parameter of an array type, the "value" of the parameter contains a reference to the array in question. Thus, any changes to the array that occur inside the method body will affect the original array that was passed as the argument.

Here's a simple example to illustrate the point:

public class Test {

  public static void main(String[] args) {
    int myNum = 1;
    int[] myArray = {1,1,1,1,1};

    myMethod(myNum, myArray);

    System.out.println("myNum is " + myNum);
    System.out.println("myArray[0] is " + myArray[0]);
  }

  public static void myMethod(int number, int[] numbers) {
    number = 2;
    numbers[0] = 2;
  }

}

Here's the output of the above code:

myNum is 1
myArray[0] is 2

You can see that the value of myNum was "protected" from change as it was passed by value to myMethod, but the contents of myArray could still be changed since the method was passed by value a copy of a reference to the original array.

Returning an Array from a Method

We can similarly use array reference variables to return arrays created inside a method back to the calling method.

Here's an example where a method called "reverse" creates a new array, filling it with the elements of an array passed to it in reverse order, and then passes that array back to the main method to be printed by yet another method, "printArray":

public class Main {

  public static void main(String[] args) {
     int[] list1 = {1, 2, 3, 4, 5, 6};
     int[] list2 = reverse(list1);
     printArray(list1);
     printArray(list2);
  } 
 
  public static int[] reverse(int[] list) {
     int[] result = new int[list.length];
     for (int i=0; i < list.length; i++) {
        result[result.length - i -1] = list[i];
     }
     return result;
  }

  public static void printArray(int[] array) {
     for (int value: array)
        System.out.print(value + "  ");
     System.out.println();
  }
}

Here's the output of the above code:

1  2  3  4  5  6  
6  5  4  3  2  1  

(Step through this code carefully, there is a lot going on here.)

2D Arrays

Sometimes, the data we need to deal with in a program fits more naturally into a table, as shown below. This is where two-dimensional arrays come in handy...

Distance Table (in miles)
  Chicago Boston New York Atlanta Miami Dallas Houston
Chicago 0 983 787 714 1375 967 1087
Boston 983 0 214 1102 1763 1723 1842
New York 787 214 0 888 1549 1548 1627
Atlanta 714 1102 888 0 661 781 810
Miami 1375 1763 1549 661 0 1426 1187
Dallas 967 1723 1548 781 1426 0 239
Houston 1087 1842 1627 810 1187 239 0

Declaring & Creating Two-Dimensional Arrays

The declaration & creation of 2D arrays is very similar to that of 1D arrays, and follows the syntax given below.

// Declare a 2D reference variable
dataType[][] myArray2D;

// Create a 10x10 array and assign its reference to a variable
myArray2D = new dataType[10][10];

// Combine declaration and creation in one statement
dataType[][] myArray2D = new dataType[10][10];

// Alternate syntax
dataType myArray2D[][] = new dataType[10][10]; \\This last one is legal, 
                                               \\but avoid it, as it
                                               \\almost always causes
                                               \\confusion

Just like you might reference an item in a table by indicating both the row and column that contain that item -- we access elements of an array by providing not one, but two indices.

Internally, a 2D array is just an 1D array whose elements are themselves 1D arrays. The first index of an element in a 2D array refers to the 1D sub-array that contains the element -- while the second index indicates the position of that element in the 1D sub-array.

The lengths of these 1D arrays (which, in many cases would correspond to the number of rows and columns you have can be accessed in a very natural way. Suppose one creates the following array:

 int[][] x = new int[3][4];

Then the structure of the 2D array and the aforementioned 1D array lengths are given by:

Filling 2D Arrays

Now suppose we wish to declare, create, and fill a 2D array with values. We can do this in a couple of ways.

We can, of course assign the values individually...

int[][] myMatrix = new int[10][10];

myMatrix [0][0] = 1;
myMatrix [0][1] = 3;
myMatrix [0][2] = 5;
...
myMatrix [0][9] = 19;
myMatrix [1][0] = 21;
myMatrix [1][1] = 23;
myMatrix [1][2] = 25;
...
myMatrix [1][9] = 39;
myMatrix [2][0] = 41;
myMatrix [2][1] = 43;
...

Alternatively, we can use a "shortcut" assignment to do the same thing::

int[][] myMatrix = {{  1,   3,   5,   7,   9,  11,  13,  15,  17,  19},
                    { 21,  23,  25,  27,  29,  31,  33,  35,  37,  39},
                    { 41,  43,  45,  47,  49,  51,  53,  55,  57,  59},
                    { 61,  63,  65,  67,  69,  71,  73,  75,  77,  79},
                    { 81,  83,  85,  87,  89,  91,  93,  95,  97,  99},
                    {101, 103, 105, 107, 109, 111, 113, 115, 117, 119},
                    {121, 123, 125, 127, 129, 131, 133, 135, 137, 139},
                    {141, 143, 145, 147, 149, 151, 153, 155, 157, 159},
                    {161, 163, 165, 167, 169, 171, 173, 175, 177, 179},
                    {181, 183, 185, 187, 189, 191, 193, 195, 197, 199}};

Although, for large arrays, even this shortcut is cumbersome. Often, we find it much easier to use a "nested" for-loop to make the assignments. Note the following does the same job as the two examples above:

int[][] myMatrix = new int[10][10];

for (int i = 0; i < myMatrix.length; i++)
   for  (int j = 0; j < myMatrix[i].length; j++)
       matrix[i][j] = 2*(10*i+j)+1;

Ragged Arrays

Interestingly, given the way a 2D array is represented internally (a 1D array of 1D arrays), we are not restricted to arrays representing aesthetically-pleasing tables where there are the same number of columns in each row.

When the "rows" (i.e., subarrays) have different lengths, we have what is known as a ragged array.

For example, array defined below has 5 "rows" (i.e., myArray.length is 5), while the length of each row differs.

int[][] myArray = {{1, 2, 3, 4, 5},
                   {2, 3, 4, 5},
                   {3, 4, 5},
                   {4, 5},
                   {5}};

for (int i=0; i < myArray.length; i++)
    System.out.print(myArray[i].length + " ");

//prints "5 4 3 2 1 "