3-1 One-Dimensional Arrays

The Road Ahead

At this point you have a solid foundation in the core syntax of Java and its object-oriented features. We’ll now turn our attention to using Java to implement common algorithms and data structures in Computer Science.

An algorithm is like a recipe; it’s a series of tasks performed in a particular order to solve a problem. We’ll look at some of the most popular algorithms for searching and sorting data and also learn about how to measure and compare the performance of algorithms using a notation called Big O.

A data structure is a collection of related information. As a budding computer scientist it’s important to not only be able to use the data structures provided by the Java API but also know how to build our own from scratch. We’ll cover a variety of data structures here including arrays, stacks, queues, and linked-lists. We’ll finish off with a look at something called the Java collections framework.

The Concept of an Array

So far the variables we have defined have been for single values; such as a number or string. The Java language includes a built-in data structure called an array for managing larger amounts of data. An array is a named sequence of related values (of the same data type).

Conceptually, you can think of an array as a vertical column of values called elements each with an index number associated with it, starting from zero (0). An array like this is called a one-dimensional array, or “1D Array” for short.

Creating and Initializing 1D Arrays

Arrays in Java are objects and there are different techniques to instantiate and initialize them. For example, the following statement instantiates an array object with 5 integer elements, and then assigns the memory location of this new array object to the numbers reference variable.

// Declare & initialize to default values (0, 0.0, false, null) in 1 step 
int[] numbers = new int[5];

1 2	// Declare & initialize to default values (0, 0.0, false, null) in 1 step int[] numbers = new int[5];

Since the array is an object, it includes a default constructor that sets each element of the array to a default starting value, either 0, 0.0, false, or null depending on the data type of the array. Here is what the result of the statement above would look like in memory:

Notice that all of the integer elements have been initialized to zero (0).

Arrays have a fixed size and type. In other words, once you create an array you cannot increase or decrease its number of elements or change its data type. If you attempt to create an array with a negative number of elements you will cause a NegativeArraySizeException to occur.

Sometimes you might know that you require an array but can’t determine its size until later in your code. To deal with this situation you can separate the declaration of the array reference variable and the instantiation of the array object into separate steps, like so:

// Declare reference variable for 1D array of integers
int[] numbers;
Scanner input = new Scanner( System.in );
int size;

System.out.print( "How many elements for array? " );
size = input.nextInt();

// And LATER in code, instantiate the actual integer array object
numbers = new int[ size ];

// Declare reference variable for 1D array of integers

int[] numbers;

Scanner input = new Scanner( System.in );

int size;

System.out.print( "How many elements for array? " );

size = input.nextInt();

// And LATER in code, instantiate the actual integer array object

numbers = new int[ size ];

The end result of this code would be similar to the 1 line version illustrated earlier but with a size determined by the user during run-time.

Finally, it’s possible to instantiate an array object and initialize each element to a starting value other than the default:

// Declare and initialize to custom starting values in 1 step
double[] marks = { 98.3, 48.1, 87.6, 75.8 };

1 2	// Declare and initialize to custom starting values in 1 step double[] marks = { 98.3, 48.1, 87.6, 75.8 };

This statement instantiates a 4 element double array object, and initializes its elements to starting values other than 0.0. In this case you don’t need to use the new keyword or specify how many elements are in the array, the Java compiler can figure this out automatically.

Indexing 1D Array Elements

Unlike strings, you can directly access an element of an array using its index. To do this you simply specify the name of the array followed by the index of the element in square brackets [ ]. An array index must always be an integer. For example:

// Use index to display the first element of marks
System.out.println( "marks[0] contains " + marks[0] );

// Add 1 to the second element of marks
marks[1]++;

// Use index to display the first element of marks

System.out.println( "marks[0] contains " + marks[0] );

// Add 1 to the second element of marks

marks[1]++;

Every array object has a public final attribute (not a method) called length that contains the number of elements in the array. Because arrays are indexed from 0, length is always 1 greater than the index of the last element of the array — be careful! You will cause an ArrayIndexOutOfBoundsException if you try to access beyond the last element in an array (or use a negative index). Furthermore, the length attribute is set once the array object is instantiated and cannot change after that. Realize that with String objects, length() is a method instead.

Array objects inherit the basic toString() method from the Object class. For example:

System.out.println( marks );

1	System.out.println( marks );

[D@1e9cd8db

The square bracket [D indicates that marks refers to an double array, and the @1e9cd8db part is the location of the array object in memory. To neatly display the elements of an array we need to process it using a loop (and there’s an even easier way that I’ll show you next time).

1D Array Processing

Counted loops are ideal for accessing array elements because we can use the control variable as an index. Consider the following code to round up then display each element in the marks array.

// Demonstrate the use of the length attribute with a counted loop
System.out.printf( "\nmarks array has %d elements\n", marks.length );
for ( int index = 0; index < marks.length; index++ ) {
    // Round up each element of the marks array
    marks[index] = Math.ceil( marks[index] );
    System.out.printf( "marks[%d] = %.1f%%\n", index, marks[index] ); 
}

// Demonstrate the use of the length attribute with a counted loop

System.out.printf( "\nmarks array has %d elements\n", marks.length );

for ( int index = 0; index < marks.length; index++ ) {

// Round up each element of the marks array

marks[index] = Math.ceil( marks[index] );

System.out.printf( "marks[%d] = %.1f%%\n", index, marks[index] );

}

marks array has 4 elements
marks[0] = 99.0%
marks[1] = 50.0%
marks[2] = 88.0%
marks[3] = 76.0%

Note how index starts from 0 and goes up to (but not including) marks.length.

The Enhanced for Loop

Java supports an enhanced version of the for loop for situations where we only need to read (not change) the elements of an array:

// Enhanced (read-only) for loop to traverse an array
System.out.print( "\nDisplay marks array using enhanced for loop: " );
for ( double mark : marks ) {
    System.out.printf( "%.1f%% ", mark );
}

// Enhanced (read-only) for loop to traverse an array

System.out.print( "\nDisplay marks array using enhanced for loop: " );

for ( double mark : marks ) {

System.out.printf( "%.1f%% ", mark );

}

Display marks array using enhanced for loop: 99.0% 50.0% 88.0% 76.0%

The loop syntax above is read as “for each mark in the marks array do the following…”. On each iteration of the loop, the mark variable is assigned a copy of the next element in the marks array. Because mark contains a copy of the element, any change to mark within the loop body does not change any array element. I hope you can see that while this style of for loop offers good readability, it’s not as versatile as the complete for loop. Without an index there is no way to change an array element.

Arrays of Objects

So far we’ve seen arrays of int and double primitive types, but what about arrays of objects, like Strings or Fractions? No problem! Let’s define an array to keep track of 4 String objects.

// Instantiate an array for 4 String objects
String[] names = new String[4];

1 2	// Instantiate an array for 4 String objects String[] names = new String[4];

An important thing to understand is that the elements of the names array cannot contain actual String objects. Rather, each element can only contain a reference to a String object. For this reason, the null reference is the default value for each element of this array.

We now need to instantiate four String objects and assign references to them to the elements of the names array.

// Instantiate String objects and assign references to names array
names[0] = new String( "Trump" );  // Don't forget: Strings are objects!
names[1] = "Obama";
names[2] = "Bush Jr.";
names[3] = "Clinton";

// Instantiate String objects and assign references to names array

names[0] = new String( "Trump" ); // Don't forget: Strings are objects!

names[1] = "Obama";

names[2] = "Bush Jr.";

names[3] = "Clinton";

For names[0] I have used the long-form way of instantiating a String object, just to remind you that Strings are in fact objects. We can now display the names using an enhanced for loop:

// Display the names
System.out.println( names.length + " recent US Presidents:");
for ( String name : names ) {
    System.out.println( name );
}

// Display the names

System.out.println( names.length + " recent US Presidents:");

for ( String name : names ) {

System.out.println( name );

}

4 recent US Presidents:
Trump
Obama
Bush Jr.
Clinton

We know that String objects are immutable, but the elements (references to String objects) in the names array can be changed. In other words, they can be reassigned to refer to a different String object in memory. The following statement:

names[0] = "The Trumpster";

1	names[0] = "The Trumpster";

instantiates a new String object and reassigns the first element of the names array to refer to it. The old “Trump” String object will be garbage collected by the JVM, assuming no other reference variables point to it. Here’s the effect in memory:

You Try!

Write a program that uses a loop to generate an integer array of 10 random integers between 1 and 100. Next, using an enhanced for loop, display all of the elements of the array.
Write a program that prompts the user to enter 5 names and store them in a String array called friends. Next, prompt the user for a name, and report to them if that name is a member of the friends array or not. Finally, display the 5 friends in the reverse order they were entered.
Using a loop, create an array of Fraction objects for the following fractions: 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, and 1/9. Using another loop, and the static add() method we defined in 2-9, calculate the sum of these 9 Fraction objects. Display the final result.