Unit 7: Arrays & ArrayLists

7.0. Overview

We've just seen how addressing the columns and rows of pixels in a graphic file (.jpg, .png, .gif) and be very useful. Pictures aren't the only places where we find it convenient to organize data by columns and rows. In this unit, we'll look at two new data structures—the Array and the ArrayList—and learn how to use loops to manipulate this data.

Let's get started.

1. Photos, and Strings as a List of characters
2. Introduction to Arrays
3. Introduction to ArrayLists
4. Simple Array Algorithms
5. Copying Arrays
6. Two-Dimensional Arrays

7.1. Photos, and Strings as a List of characters

This next unit is perhaps the single most important unit that we'll be covering all year.

Pay close attention! :)

7.1.0. Photos → Arrays

There are a couple of reasons that we've taken some time to play with the idea of manipulating photos here. One is that it's fun, and photos give us visual feedback that is otherwise sometimes hard to get from our abstract programming.

The second, more important, reason is that we're about to start studying data structures—structures (like int, double, and boolean variables) that store data—and if you think about it, photos are a type of data structure. A photo is composed of subsets of data—the pixels—each of which can be accessed by referring to column and row (x and y, or i and j, etc), which are called the indexes of the data. The array of rows running down the height of a picture, and the array of columns running across the width of each row, represent a type of data structure called... an Array. Our next unit looks at ways that we can create Arrays and ArrayLists to store and manipulate data.

Our photos are composed of objects of the Color class called pixels, each of which in turn contains smaller subsets of data—its RGB values—that can be accessed by methods like .getRed(), .getGreen(), and .getBlue(). We can alter these RGB values as well, obviously, or use their values in calculating information that can be used to create new objects.

Likewise, we'll soon see that Arrays and ArrayLists can store collections of objects that may very well contain subsets of data.

7.1.2. A String is a one-dimensional "array" of letters

A String is simply a collection of characters in sequence. We can access any single letter in a string by using the substring method.

public String replace(String sentence, String letter)
{
    String newSentence = "";
    for (int i = 0; i < sentence.length(); i++)
    {
        if (sentence.substring(i, i+1).equals(letter))
        {
            newSentence = newSentence + "*";
        }
        else
        {
            newSentence = newSentence + sentence.substring(i, i+1);
        }
    }
    return newSentence;
}

7.2. Introduction to Arrays

System.out.println("I have " + friends.length + "friends.");

It's easy to depict graphically an Array called primes containing the first ten primes in it.

Just as with any variable storing data, the array has to be declared and then initialized before it can be used.

double[] myData;

myData = new double[10];

double[] myData = new double[10];

int[] fibNums = {1, 1, 2, 3, 5, 8, 13, 21};

In most cases, an "initialized" the array doesn't actually have the values stored in it yet that we want it to have.

How do you put values into an array?

for (int i = 0; i < myData.length; i++)
{
    System.out.print("Enter value #" + i);
    myData[i] = in.nextDouble();
}

// Assume that primes is an Array that
// includes a series of prime numbers

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

Arrays can hold any type of data you want: int, double, String, even objects. A bank, for example, might have software that keeps track of all its bank accounts:

BankAccount[] bank = new BankAccount[1000];

That array of BankAccount account objects, once it has been filled, could be visualized like this:

7.2.1. Playing with Arrays

Cheater.

int[] randNums = new int[200];
for (int i = 0; i < 200; i++)
{
    randNums[i] = (int) (Math.random() * 201) - 100;  // tricky! potential off-by-one problem
}

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

7.2.2. Advantages, disadvantages, and things to look out for

Arrays are a great way to store a collection of data, but one of their disadvantages is the fact that they have a fixed size. Once you've declared the array to have a size of 10, or 100, or 10000, that's all the data you can store. Manipulating arrays is relatively fast because once you create them, memory is allocated and the computer doesn't have to do any dynamic management of the memory space. So, the Array structure is fast, but inflexible.

(Ultimately, if you really need to expand your array you can create a new, larger one, and copy over the data from your first array, but that's a pain, and a slow process. You typically want to avoid this.)

Other things to note about arrays:

An important strategy:

/**
 * A Demo of a partially-filled array
 */

import java.util.Scanner;

public class FavoriteMovies
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String[] movies = new String[100];
        int size = 0;   // simultaneously indicates
                        // size and next element to
                        // be updated.
        System.out.print("Enter a favorite movie: ");
        String movie = in.nextLine();
        while (!movie.equals(""))
        {
            movies[size] = movie;  // save movie
            size++;                // increment size
            System.out.print("Another? ([Enter] to quit): ");
            movie = in.nextLine();
        }
        System.out.println("Here are your movies!");
        for (int i = 0; i < size; i++)
        {
            System.out.println(movies[i]);
        }
    }
}

String[] badWords = {"poop","stupid","dumb",
                     "darn","dagnabbit","damn"};

Scanner in = new Scanner(System.in);
System.out.println("Enter a sentence, and keep it clean: ");
String oldSentence = in.nextLine();

Enter a sentence, and keep it clean: 
This is a dumb, stupid assignment. I'd rather be wearing poopy diapers, darnit!

Sanitized:
This is a ****, ****** assignment. I'd rather be wearing ****y diapers, ****it!

7.3. Overview - Introduction to ArrayLists

There are two main kinds of Lists, or sequences, in Java. We've already seen the Array, and now we turn to the ArrayList.

7.3.1. Intro to ArrayLists

Arrays are a powerful construct, but in many circumstances, using them can be a bit clunkier than it needs to be. And just as the while loop is really all you need to compute—the for loop isn't strictly necessary, but it's awfully nice to have in certain situations—we have an additional type of array structure that we can use to manage sets of data. It's the ArrayList.

Declaring an ArrayList is different from declaring an Array. Note the differences (using random number arrays):

int[] randNums = new int[200];
for (int i = 0; i < 200; i++)
{
    randNums[i] = (int) (Math.random() * 100) + 1;  
}

// We have to import the ArrayList package
import java.util.ArrayList;    
    
ArrayList<Integer> randNums = new ArrayList<Integer>(); 
// why the capital I??!

for (int i = 0; i < 100; i++)
{  
    randNums.add((int) (Math.random() * 100) + 1);
}

7.3.2. An Intro to the Bank class

Imagine that you want to keep track of a number of BankAccounts. How would you do that?

We could certainly use an Array of BankAccount objects, but we'd have to make sure that we reserved enough space for every account in the bank.

Another strategy is to use the dynamically-sized ArrayList.

import java.util.ArrayList;

public class Bank
{
    // instance variables
    private ArrayList<BankAccount> accounts;

    /**
     * Constructs an empty ArrayList for the bank with no bank accounts
     */
    public Bank()
    {
        accounts = new ArrayList<BankAccount>();
    }
    
    /**
     * Adds an account to this bank
     * @param  a   the account to add 
     */
    public void addAccount (BankAccount newAccount)
    {
        accounts.add(newAccount);
    }
    .
    .
    .

We use angle brackets < > when declaring the clientAccounts array to indicate that BankAccount is a type parameter. Because the ArrayList is a generic class, we have to specify what type of data we're going to store in the ArrayList.

What's the initial length of an ArrayList? It's 0 because we haven't yet stored anything in it. We can check the size of the array by using the ArrayList method .size():

System.out.println(clientAccounts.size());
→ 0

To add an element to our array:

clientAccounts.add(new BankAccount(1001));

Now, what's the output of this statement?

System.out.println(clientAccounts.size());
→ 1

In the BankAccount class we had a .getBalance() method. How would you print out the balance from the this first account?

// NOT System.out.println(clientAccounts[0].getBalance());     :( 

7.3.3. ArrayList Methods

With ArrayLists, we need a method to get the data out of the objects:

System.out.println(clientAccounts.get(0).getBalance());

There are other methods that we can use to manipulate an ArrayList:

• .add(anObject) adds an element to the end of the ArrayList
• .add(position, anObject) inserts an element into that position
• .set(position, anObject) replaces the element at position with anObject
• .remove(position) deletes the object at the position

It's important to understand that because an ArrayList is able to expand and contract dynamically to fit the data, values may move up and down in the list, depending on how other elements are manipulated.

ArrayList<String> monsters = new ArrayList<String>();
monsters.add("Dracula");
monsters.add("Nessie");
monsters.add(1, "Godzilla");
monsters.add("Sulley");
monsters.set(2, "The Beast with 5 Fingers");
monsters.remove(0);
System.out.println(monsters.get(1));

7.3.4. Wrappers

Another minor (and temporary) problem with using ArrayLists: they only work with objects.

Almost everything in Java is an object, except for the primitive types. Remember these?

• boolean
• byte
• char
• double
• float
• int
• long
• short

Anything else—Strings, dogs, BankAccounts—are objects.

So how can we set up an ArrayList to work with things that aren't objects? How do I set up an array of integers?

Java has wrapper classes—classes that "wrap around" each primitive type and create an object version of it—that you can use to automatically create ArrayLists with the primitives.

So this is illegal:

ArrayList<int> primes = new ArrayList<int>();

But the wrapper for the int class is Integer. So we can do this:

ArrayList<Integer> primes = new ArrayList<Integer>();

The wrapper classes for the eight types of primitives are these. Note that all of the classes are capitalized, and two of them have the name changed.

Primitive   Object wrapper  
---------   --------------

boolean     Boolean
byte        Byte
char        Character
double      Double
float       Float
int         Integer
long        Long
short       Short

7.3.5. Auto-boxing

Okay, so let's say I want to store a bunch of prime numbers in an array list. How do I need to get started on that?

1. Declare the ArrayList

   ArrayList<Integer> primes = new ArrayList<Integer>();

2. Find the first prime and put it in there.

Can I do this?

primes.add(2);

This is tricky because 2 is of the type int, but the primes ArrayList is of the type Integer, and those are two separate things. So what does Java do?

It turns out that Java does something called Auto-boxing, which would have been better identified as auto-wrapping, as textbook author Cay Horstmann points out. If we write

Integer aPrime = 2;

...Java automatically wraps the int 2 into an Integer object, and places it in aPrime without any fuss.

Likewise, if we write

int firstPrime = aPrime;

...the Integer value is automatically "unboxed" into an int value with no problem.

This process of auto-boxing (auto-wrapping) and auto-unboxing happens transparently in all recent versions of Java.

So, back to the original question. Does primes.add(2); work? Yes. The 2 is auto-wrapped from an int to an Integer, and the program works as it should.

7.3.6. Working with Loops and Collections (Arrays and ArrayLists):
The Enhanced for loop

Just as the for loop is a special case of the while loop, and more convenient for situations in which you're just counting through a series of numbers, the enhanced for loop is just a special case of the for loop.

// Example of an enhanced for loop
// @precondition myFriends is a String Array

for (String friend : myFriends)
{
    System.out.println(friend);
}

Here are two loops, showing the similarities and differences between a for loop and an enhanced for loop.

// Classic for-loop with an array

// for loop to add all numbers in a dataList
// @precondition dataList is an ArrayList with numeric values in it

double sum = 0;
for (int i = 0; i < dataList.size(); i++)
{
    sum = sum + dataList.get(i);
}

// Enhanced for loop with an array
// @precondition dataList is an ArrayList with numeric values in it

// enhanced for loop to sum numbers in a dataList
double sum = 0;
for (double data : dataList)   // Read as "for each data in dataList..."
{
    sum = sum + data;
}

The difference between these two loops is that, in the first one, the variable i is getting the index of the variable in the array, and we use that index to access the contents of each element in the array. In the second one—the enhanced for loop—the loop variable is getting the actual values from each element in the array.

Enhanced for loops don't work for every situation—they're best when you have to go through an entire array of information, either looking for something or performing an action on every element in the array. If you don't need to do that, then you shouldn't be using an enhanced for loop—you should use a regular for loop, or maybe a while loop.

7.4. Overview - Simple Array Algorithms

By using Arrays and ArrayLists within a loop, we can accomplish some amazing things. Let's get started!

7.4.1. Filling an Array

To fill an array, set up loops as needed to iterate through the elements in that array.

If it's an Array and it won't be completely filled, you'll need to include a variable to track its currentSize.

Show/hide example of filling an array

/**
 * The ArrayFiller class adds values into an array, one at a time
 * 
 * @author Richard White 
 * @version 2016-11-16
 */

public class ArrayFiller
{
    // instance variables
    private double[] values;
    private int currentSize;
    private static final int MAX_SIZE = 100;

    /**
     * Constructor for objects of class ArrayFiller
     */
    public ArrayFiller()
    {
        values = new double[MAX_SIZE];
        currentSize = 0;
    }

    /**
     * The add method adds an element to the array, if possible
     * @param  value   a double value to be added to the array
     * @return 0 if successful, -1 otherwise 
     */
    public int add(double value)
    {
        if (currentSize < MAX_SIZE)
        {
            values[currentSize] = value;
            currentSize++;
            return 0;
        }
        else
        {
            return -1;
        }
    }
    
    /**
     * The toString method returns a string with all the elements of
     * the array in it.
     * @return a String with the values separated by commas.
     */
    public String toString()
    {
        String theArray = "";
        for (int i = 0; i < currentSize; i++)
        {
            if (i > 0)
                theArray += ",";
            theArray += String.valueOf(values[i]);
        }
        return theArray;
    }
}

7.4.2. Finding the Sum/Average

To find the sum of values in an array, create a loop that goes through the entire array, adding each element found into a sum variable.

To find the average of those values, divide the sum by the number of values (ie. the length of the array).

// precondition: the ArrayList vals contains a series of integers
double sum = 0;
for (int i = 0; i < vals.size(); i++)
{
    sum += vals.get(i);
}
double average = sum / vals.size();

7.4.3. Finding the Maximum or Minimum

The strategy for finding the maximum value in a list is pretty simple, and mimics what you might do if you were trying to do the same thing by hand:

1. Look at the first item on the list. Remember it, because that's the biggest number you've seen so far.
2. Go to the next item on the list. If it's bigger, remember that as the new biggest number you've seen so far. (You'll want to decide whether you want to remember the value itself, or its location in the list.)
3. Repeat step 2 until you've gone through every item on the list.

Show/hide code

// given a dataList of Double values...
double maxValue = dataList.get(0);
for (int i = 1; i < dataList.size(); i++)
{
    if (dataList.get(i) > maxValue) 
        maxValue = dataList.get(i);
}
System.out.println("The biggest value seen was " + maxValue);

It's probably prudent to include a check before we start looking through the list, to make sure that there are items in the list:

if (dataList.size() == 0)
    System.out.println("Error: no items on list")
else
{
    .
    .
    .

The same strategy works for looking for the minimum value on a list.

7.4.4. Finding a Value

Looking for values in an Array or ArrayList is an entire branch of computer science itself, and we'll do a unit exploring that topic later on in the course. For now, we can perform a linear search by going through our array one element at a time and looking for specific "search keys." If we reach the end of the array without having found the key(s), then they don't exist in our array.

public int findString(ArrayList<String> words, String searchValue)
{
    for (int i = 0; i < words.size(); i++)
    {
        if (words.get(i).equals(searchValue))
        {
            return i;
        }
    }    
    return -1;  // we didn't find the searchValue
}

7.4.5. Inserting an Element into an Array

If you just need to add an element to an unfilled Array or ArrayList, the easiest place to put it is at the end of the list. If you're adding to a partially-filled Array, be sure to increment the currentSize counter as well.

// Adding values at the end of the valueArray and the valueArrayList
valueArrayList.add(newValue);

if (currentSize < valueArray.length)
{
    valueArray[currentSize] = newValue;
    currentSize++;
}

If you need to insert an element into the middle of an array—say a list of numbers that have already been sorted—you'll need to first identify how far down to insert the number, and then make sure to shift all the numbers after that location down one place to make room for the insertion.

// Inserting values into the middle of valueArrayList
valueArray.add(location, newValue);

// Inserting values into the middle of valArray
currentSize = currentSize + 1;
for (int i = currentSize; i > insertLocation; i--)
{
    valArray[i] = valArray[i - 1];
}
valArray[insertLocation] = newValue;

7.4.6. Deleting an Element from an Array

Deleting an element from an array typically requires finding where that element is located and then removing it from the list.

If you're working with an Array, you'll need to shift all the elements below that item up in the order so as not to leave any blank spots. You'll also have to change the value of currentSize.

7.4.7. Swapping Two Elements in an Array

To swap the contents of two elements, set up a temporary variable that can hold the contents of one of the elements while the exchange is made:

String[] friends = {"Gary", "Dana", "Cheryl", "Lance"};
// Swap the first and last friends on my list
String tmp = friends[0];
friends[0] = friends[friends.length - 1];
friends[friends.length - 1] = tmp;

7.4.8 Counting Matches

Often you'll need to identify how many sets of data match a certain condition.

We've already seen this in the Bank class example. Which of the methods in that class went through and identified accounts that met a certain condition?

/**
 * Counts the number of bank accounts whose balance is at least 
 * a given value
 * @param atLeast  the balance required to count an account
 * @return the number of accounts having at least the given balance
 */
public int count (double atLeast)
{
    int matches = 0;
    for (BankAccount a : accounts)
    {
        if (a.getBalance() >= atLeast) matches++;
    }
    return matches;
}

The count method counted bank accounts that met a certain minimum balance requirement. This method also used an enhanced for loop to go through all the accounts, which is a good example of how that works.

7.5. Copying Arrays

Copying arrays can be a tricky thing for a couple of reasons.

1. There's the risk of creating a new reference to a single array, rather than a new copy of an array.

   String[] friends = new String[3];  
   String[] enemies = friends; // copying an empty array?? (No!)
   friends[0] = "Aaron";
   System.out.println(enemies[0]); // --> Prints Aaron

2. There's the risk of performing only a shallow copy of an array, when a deep copy is what is wanted.

There's more to discuss here than we need to at this point, so let's just look at a simple copy of an array.

Copy-run this code to better understand the difference between creating a new reference to an array and creating a new copy of an array.

/**
 * Demonstrates that copying arrays is difficult!
 */
import java.util.Arrays;    // utility used to sort our array easily

public class ArrayCopyDemo
{
    public static void main(String[] args)
    {
        int[] arr1 = {5,4,3,2,1};
        int[] arr2 = arr1;      // trying to make a copy (incorrectly)
        Arrays.sort(arr2);      // I'll just sort the second array...
        for (int val : arr1)    // ... but when I print out the first array...
            System.out.print(val + " ");
        System.out.println();   // IT GOT SORTED! arr2 was just a reference
                                // to arr1.
                                
                                // But I want a separate copy! How?
        
        int[] arr3 = {5,4,3,2,1};               // Try again. Original array
        int[] arr4 = new int[arr3.length];      // Creating a NEW array of the same length
        for (int i = 0; i < arr3.length; i++)   // Manually copying
        {                                       // over every item
            arr4[i] = arr3[i];                  // in that array (a "deep copy")
        }
        Arrays.sort(arr4);                      // Sorting just array4
        for (int val : arr3)                    // When I print out array 3
            System.out.print(val + " ");        // It is still unsorted,
        System.out.println();                   // just like I wanted.
    }
}

7.6. Overview - Two-Dimensional Arrays

We've spent a little bit of time looking at Arrays and ArrayLists. You should be comfortable with the differences between these two data structures before we go any farther (see below).

Now we're moving onto two-dimensional arrays, which give us even more power.

7.6.1 Review of Arrays and ArrayLists

Recall the salient details of Arrays and ArrayLists:

7.6.2. Intro to Two-Dimensional Arrays

We've already seen a bit of an introduction to 2-Dimensional data when we used nested loops to access the columns and rows of a rectangular image file.

for (int row = 0; row < height; row++)
{
    for (int col = 0; col < width; col++)
    {
        // do things that reference col,row
    }
}

... and we've already used one-dimensional loops to go through a simple Array or ArrayList of data. It shouldn't be any surprise, then, that we can use nested loops to go through a 2-dimensional Array of Arrays.

Multi-dimensional arrays in Java are almost always Arrays and not ArrayLists. Trying to access a 2-d array list becomes more difficult to do conceptually, and more expensive for the processor, so we're going to restrict our 2-D activities to official Arrays. Remember that arrays have to have their dimensions specified ahead of time.

final int ROWS = 480;
final int COLS = 640;
int[][] board = new int[ROWS][COLS];

Unlike your typical x-y coordinate system, Java is considered "row major," in that the row specification comes first, and then the column. You can visualize a two-dimensional array as an array of arrays:

board[0]   →  [0, 1, 2, 3, 4, ... , 639]
board[1]   →  [0, 1, 2, 3, 4, ... , 639]
board[2]   →  [0, 1, 2, 3, 4, ... , 639]
   .
   .
   .
board[479]   →  [0, 1, 2, 3, 4, ... , 639]

To access the information in that array, you often use nested loops, again, just as we did with the photo:

for (int row = 0; row < ROWS; row++)
{
    for (int col = 0; col < COLS; col++)
    {
        // do stuff to board[row][col]
    }
}

7.6.3. Sparse Arrays

Some multi-dimensional arrays—2-D arrays, 3-D arrays, or even more—contain a lot of information in them, and require using a full, multi-dimensional space for keeping track of all that information.

An array that keeps track of the state of every cell in a GameOfLife simulation, for example, needs to continuously track the state of every single cell.

Likewise, a RandomWalker that is exploring a two-dimensional area of space might need to be tracked so that we can display every cell that it has been to... and then we can display information about that cell, including perhaps a "heat map," color-coded so that we have a visual record of where the walker has spent more of its time.

There may be multi-dimensional contexts, however, where the amount of information that we're tracking in the array is quite a bit smaller. A 2-dimensional array for a RandomWalker, for example, might be 100 × 100 cells, requiring a full 10000 array elements of memory, and maybe the walker isn't going to travel to all of those cells.

Or you might imagine an astronomer that needs to keep track of stars in the night sky. A map of the night sky would encompass a large amount of space, but the stars being monitored only occupy a few data points in that space. The sky is sparsely populated by those stars.

In situations where there is a large "data space" but not much actual "data," the array is considered a sparse array.

For these situations, the information can usually be stored in a more efficient way: rather than maintaining a large collection of data cells, most of which are empty, we'll maintain a small list of those locations, identifying them by their coordinates and values:

• 4, 7, value
• 50, 21, value
• 90, 67, value
• 37, 91, value

Because each item on this list stores multiple pieces of information, a class is often written to store the information, and objects of that class maintained in an Array or ArrayList.