Arrays and References

Arrays and References
An Introduction with Examples in Java

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

Using Arrays
Understanding Arrays
Programming Patterns: Conformal Arrays, Lookup Arrays, and Accumulator Arrays
Objects and References

Review: An Array in Memory

Review: Requirements

Fixed and Known Number of Elements:
- In order to be able to allocate a contiguous block of memory
Homogeneous Elements:
- In order to know how big each element/offset is

Arrays and References

Things You Know About Java:
- The new operator is used to allocate memory for arrays
- The new operator returns a reference
Conclusion:
- Arrays must be reference types in Java
0-Based Indexing:
- The first element has an index of 0 since indexes correspond to offsets from the first memory address.
- Nerd Humor
  
  (Courtesy of xkcd)

An Example of Declaration and Instantiation

We can now look more closely at what happens when an array is declared and when it is instantiated.

// Allocate four bytes to hold the address of the array // when it is created. Add scores to the name table. // int[] scores; // Allocate (from the heap) enough memory to hold // 5 int-values (20 bytes in total), initialize // each element to 0, and assign 5 to the // final attribute named length (at that address). // // Then, store the address in the four bytes // named scores. // scores = new int[5];

An Example of Declaration and Instantiation (cont.)

images/JavaMemoryModel_IntArrayExample.png

The [ ] Operator

Purpose:
- Access an element of an array
Internals:
- Performs reference/address arithmetic
Continuing the Example:
// Assign the value 10 to the memory location // at the address of scores plus the size of 1 int-value // (i.e., scores plus 4) // scores[1] = 10; // Retrieve the value located in the memory location // at the address scores plus 4 bytes and print it // (i.e., print the value 10) // System.out.printf("%d\n", scores[1]);

The Assignment Operator

In General:
- Assign what is on the right side to the variable on the left side
Arrays:
- This involves the assignment of a reference
An Example:
String[] aka, original; original = new String[3]; original[0] = "Federal Bureau of Investigation"; original[1] = "Central Intelligence Agency"; original[2] = "Department of Transportation"; aka = original; // aka and original contain the same reference // (i.e., are aliases) aka[0] = "FBI"; // This will print "FBI" // System.out.println(original[0]);

An Example of Arrays of Objects

An array of objects is really an array of references.

// Allocate four bytes to hold the address of the array // when it is created. Add identity to the name table. // Color[] identity; // Allocate enough memory to hold 2 addresses (8 bytes in total), // initialize each element to null, assign to to the (final) attribute // named length (at that address), and store the address of the // array in the four bytes named identity. // identity = new Color[2]; // Allocate memory to hold each Color, initialize // the attributes of the objects, and put the address // in the appropriate element in the array. // identity[0] = new Color( 69, 0, 132); identity[1] = new Color(173, 156, 101);

An Example of Arrays of Objects (cont.)

images/JavaMemoryModel_ColorArrayExample.png

Arrays Declared to be final

The fact that arrays are reference types leads to some "surprises" about arrays that are declared to be final. Specifically, a reference can only be assigned to the array once, but values/references can be assigned to the elements of the array multiple times.

final int[] range; range = new int[2]; range[0] = 0; range[1] = 100; // These lines will compile range[0] = -1000; range[1] = 1000; // This line will not compile range = new int[2];

Comparing Arrays

The relational equals operator (i.e., ==) compares references. To compare elements, use the array's .equals() method or the Arrays.equals() method, but be careful since they rely on the elements .equals() method which may not do what you want.

javaexamples/basics/AkaArrays.java (Fragment: 0)

Arrays as Parameters

A copy of the reference is passed so the formal parameter is an alias for the actual parameter.

// This function will swap the values of // elements 0 and 1 in the array duo // public static void swapElements(int[] duo) { int temp; temp = duo[0]; duo[0] = duo[1]; duo[1] = temp; }

Arrays as Attributes

The Idea:
- An object has an attribute that consists of multiple homogeneous elements (i.e., an array)
An Important Consideration:
- Should/does the object allocate memory for the array in the constructor or should/is the array passed to the constructor

Arrays as Attributes (cont.)

Allocating Memory in the Constructor

public class GradeBook { private double[] grades; private String course; public GradeBook(String c, int n) { this.course = c; this.grades = new double[n]; } // ... public double getGrade(int index) { if (index < this.grades.length) return this.grades[index]; else return -1; } }

GradeBook gb; gb = new GradeBook("CS100", 3); // ... System.out.printf("Grade %d: %f5.1\n", i, gb.getGrade(i));

Arrays as Attributes (cont.)

Passing the Array to the Constructor

public class GradeBook { private double[] grades; private String course; public GradeBook(String c, double[] g) { this.course = c; this.grades = g; } // ... public double getGrade(int index) { if (index < this.grades.length) return this.grades[index]; else return -1; } }

double[] exams = {100.0, 95.0, 100.0}; GradeBook gb; gb = new GradeBook("CS100", exams); // ... System.out.printf("Grade %d: %f5.1\n", 1, gb.getGrade(1)); exams[1] = 10.0; System.out.printf("Grade %d: %f5.1\n", 1, gb.getGrade(1));

Arrays as Attributes (cont.)

Passing and Copying the Array

public class GradeBook { private double[] grades; private String course; public GradeBook(String c, double[] g) { int n; this.course = c; n = g.length; this.grades = new double[n]; for (int i = 0; i < n; i++) { this.grades[i] = g[i]; } } }

double[] exams = {100.0, 95.0, 100.0}; GradeBook gb; gb = new GradeBook("CS100", exams); // ... System.out.printf("Grade %d: %f5.1\n", 1, gb.getGrade(1)); exams[1] = 10.0; System.out.printf("Grade %d: %f5.1\n", 1, gb.getGrade(1));

Arrays as Attributes (cont.)

The Obvious Question:
- Which is correct/better?
An (Unfortunate) Truth:
- It depends on the situation

The clone() Method

clone() creates a shallow copy so each element in copy will contain the same reference as the corresponding element in original

Movie[] copy, original; original = new Movie[4]; original[0] = new Movie("Shrek", 2001); original[1] = new Movie("Toy Story", 1995); original[2] = new Movie("Monsters, Inc.", 2001); original[3] = new Movie("Who Framed Roger Rabbit", 1988) ; copy = original.clone();

java.util.Arrays Revisited

The methods in the java.util.Arrays utility class can change the elements in the arrays that they are passed because arrays are reference types.

import java.util.Arrays; int target; int[] a; a = new int[100]; Arrays.fill(a, 0); // Fill a with zeroes Arrays.fill(a, 1, 10, 99) // Fill a[10] thru a[99] with ones ... Arrays.sort(a); // Sort a in ascending order

An Aside: Variable-Length Parameter Lists

The Issue:
- It is sometimes convenient to write a method that can be passed a variable number of parameters (e.g., a max() method)
One Solution:
- Use an array instead
The Shortcomings:
- Is very inconvenient when the actual parameters are literals (since an array needs to be constructed
- Can also be inconvenient when the actual parameters are variables

Variable-Length Parameter Lists (cont.)

A More Syntactically Convenient Solution:
- Indicate that a formal parameter can actually be multiple parameters of that type
The Java Syntax:
- Use ... after the type of the last formal parameter
Using the Formal Parameter:
- The formal parameter can be used as if it were an array (of copies of) the actual parameters

Variable-Length Parameter Lists (cont.)

javaexamples/variadic/Numeric.java (Fragment: 0)

javaexamples/variadic/Driver.java (Fragment: 0)

There's Always More to Learn