Welcome to Lesson 5!

Learning Objectives for Today's Lesson

By the end of today's lesson, you should know...
  • What is a multi-dimensional array?
  • How do you declare a multi-dimensional array?
  • How do print a multi-dimensional array?
  • What are some applications of multi-dimensional arrays?
  • What is a ragged array?
  • What is an ArrayList?
  • How does an ArrayList compare to an array?
  • How do you declare an ArrayList variable?
  • How do you access data in an ArrayList?
  • How do you get the size of an ArrayList?
  • How do you add and remove data from an ArrayList?
  • How do you search for data in an ArrayList?
  • How do you set the value at a specified index in the ArrayList?
  • What type of data can ArrayLists store?



1. Multidimensional Arrays

Introducing Multidimensional Arrays

  • The arrays we have written so far can only hold one column of data.
  • But, one array can also hold two or more columns of data.
  • An array storing multiple columns is known as a multidimensional array
  • As an example, think of a spreadsheet with rows and columns.
  • If you have 4 rows and 3 columns then your spreadsheet can hold 12 numbers
    double scores[][] = new double[4][3];
    
  • The above is known as a two dimensional array.
  • Arrays can also hold store data in more than two dimensions.
  • For example:
        double scores[][][] = new double[4][3][2];
  • Each added dimension requires one more pair of square braces
  • We will focus on two-dimensional (2D) arrays in this section
  • You then use similar techniques for multidimensional arrays

Rows and Columns

  • Two-dimensional (2D) arrays are like a spreadsheet or table
    • First dimension is the row
    • Second dimension is the column
    data[row][col]
    • Array elements are the intersection of a row and column
  • For the array named data:

    data[0][0] data[0][1] data[0][2]
    data[1][0] data[1][1] data[1][2]


Declaring and Allocating 2D Arrays
  • To declare as a 2D int array:
    int[][] data;
    

    or

    int data[][];
    

    or even

    int[] data[];
    
  • Declaring an Array Size:
    int data[][];
    data = new int[2][3];
    

    or

    int[][] data = new int[2][3];
    

    or

    int[][] data = new int[2][];
    data[0] = new int[3];
    data[1] = new int[3];
    

Initializing 2D Arrays
  • Like one-dimensional arrays, 2D array elements are assigned default values based on the array type:
    • Integer (byte, short, int, long): 0
    • Floating-point (float, double): 0.0
    • Character (char): '\u0000'
    • Boolean: false
    • Objects: null
  • You can initialize 2D arrays with static initializers or loops
  • For example: 2 row by 3 column array using static initializers:
    int[][] data = {{1,2,3}, {4,5,6}};
    
  • Alternately, you can use non-static initialization to declare an array and assign it the same values:
int[][] data = new int[2][3];
data[0][0] = 1;
data[0][1] = 2;
data[0][2] = 3;
data[1][0] = 4;
data[1][1] = 5;
data[1][2] = 6;
  • Here is a representation of the above array

123
4
5
6
  • You can process multi-D arrays by nesting loops
  • Each loop has its own counter that corresponds to an index
1
2
3
4
5
6
7
8
9
10
11
12
public class Array2D {
    public static void main(String[] args) {
        int[][] data = {{1, 2, 3}, {2, 4, 6}};
        for (int i = 0; i < data.length; i++) {
            System.out.print("Row " + i + ": ");
            for (int j = 0; j < data[i].length; j++) {
                System.out.print(data[i][j] + ", ");
            }
            System.out.println();
        }
    }
}
  • Produces the output:
    Row 0: 1, 2, 3,
    Row 1: 2, 4, 6,
    

Example: Creating a Table

  • Methods may have multi-D array parameters
  • Methods may return a multi-D array as the value returned
  • Similar to 1D arrays, but with more brackets
  • Example: 2D int array of the multiplication table

Example of a Two-Dimensional Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class MultTable {
    
    public static void main(String[] args) {
int[][] table = makeTable(9);
print(table);
}

public static int[][] makeTable(int size) {
int[][] table = new int[size][size];
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[i].length; j++) {
table[i][j] = (i + 1) * (j + 1);
}
}
return table;
}

public static void print(int[][] table) {
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[i].length; j++) {
if (table[i][j] < 10) { //line up columns for single digit #s
System.out.print(" ");
}
System.out.print(table[i][j] + " ");
}
System.out.println();
}
} }
Notes on the Code
  • Method makeTable returns a 2D table
    public static int[][] makeTable(int size) {
    
  • Method print takes a 2D int array as a parameter
    public static void print(int[][] table) {
    
Ragged Arrays
  • Ragged arrays have rows of unequal length
  • Rows can have arrays assigned of different lengths
  • Produces rows with different numbers of columns
  • For example:
    int data[][];
    data = new int[3][];  // allocate columns
    data[0] = new int[5]; // allocate row 0
    data[1] = new int[0]; // allocate row 1
    data[2] = new int[3]; // allocate row 2
    
  • Can also use static initialization and get the same result:
    int[][] data = {{1,2,3,4,5}, {}, {6,7,8}};
    

Example of a Ragged Array

1
2
3
4
5
6
7
8
9
10
11
12
public class ArrayRagged {
    public static void main(String[] args) {
        int[][] data = {{1,2,3,4,5}, {}, {6,7,8}};
        for (int i = 0; i < data.length; i++) {
            System.out.print("Row " + i + ": ");
            for (int j = 0; j < data[i].length; j++) {
                System.out.print(data[i][j] + ", ");
            }
            System.out.println();
        }
    }
}

Activity 5.1: Tic-Tac-Toe in 2D (10 pts)

Tic-Tac-Toe board
image source

  • Create a new Java project called TicTacToe2d and copy and Paste the below starter code into a file named TicTacToe2d.java
  • For this activity, we will create a Tic-Tac-Toe board stored in a two-dimensional array
  • Your job is to fill in the missing lines of code where indicated.
  • When your program is running properly (see sample output below), submit it to Canvas.

Starter Code:

/**
 * @author
 * CIS 36b
 * Activity 5.1
 */

import java.util.Random;
import java.util.Scanner;

public class TicTacToe2d {
    /**
     * Initializes the board by assigning all array elements the value of '-'
     * @param board the array representing the tic-tac-toe board
     */
    public static void initializeBoard(String board[][]) {

        //Fill in missing method body here

    }
   
    /**
     * Prints the board to the console in the form of a grid,
     * including column and row numbers
     * @param board the array representing the tic-tac-toe board
     */
    public static void printBoard(String board[][]) {
        System.out.print("\nTic-Tac-Toe:\n ");
        for (int i = 1; i <= 3; i++) {
            System.out.print(" " + i);
        }
        System.out.println();
       
        for (int i = 0; i < board.length; i++) {
            System.out.print((i + 1) + " ");

            //fill in for loop here

            System.out.println();
           
        }
    }

/**
* Determines whether a particular position
* on the board has already been taken.
* @param board the array representing the game board
* @param row the row to check
* @param col the column to check
* @return whether that position has already been taken
*/

    public static boolean alreadyTaken(String board[][], int row, int col) {
        return (!board[row - 1][col - 1].equals("-"));
    }

/**
* Places an X or O into the correct position on the board.
* Called when either the player or computer makes its move.
* @param board the array representing the tic-tac-toe board
* @param row the row in the array at which to place the X or O
* @param col the column in the array at which to place the X or O
* @param character either X or O
*/

    public static void makePlacement(String board[][], int row, int col, String character) {

        //fill in missing line here

    }
   
    /**
     * Gives a random position on the board
     * Used for generating moves by the computer
     * @return a random row or column
     */
    public static int randomPosition() {
        final int SIZE = 3; //3 X 3 array
        Random r = new Random(System.currentTimeMillis());
        return r.nextInt(SIZE) + 1;
       
    }
   
    /**
     * Determines whether three Strings are all Xs or all Os
     * Used as a helper method to the gameOver method
     * @param a the first
String to compare, either X, O, or -
     * @param b the second
String to compare, either X, O, or -
     * @param c the third
String to compare, either X, O or -
     * @return whether the
Strings are all Xs or all Os
     */
    public static boolean threeInRow(String a, String b, String c) {
        if (a.equals(b) && b.equals(c) && ! a.equals("-")) {
            return true;
        }
        return false;
    }
   
    /**
     * Determines whether the game is over
     * due to one player winning, using
     * a series of if statements.
     * Calls the threeInRow method for each
     * possible row on the board.
     * @param board the tic-tac-toe game board
     * @return whether the game is over
     */
    public static boolean gameOverWinner(String board[][]) {
        boolean winner = false;

        //Check if winning across

        if (threeInRow(board[0][0], board[0][1], board[0][2])) {
            winner = true;
        } else if (threeInRow(board[1][0], board[1][1], board[1][2])) {
            winner = true;
        } else if (threeInRow(board[2][0], board[2][1], board[2][2])) {
            winner = true;

        //Fill in the missing 3 else if statements for winning going down

        //Check if winning diagonally

        } else if(threeInRow(board[0][0], board[1][1], board[2][2])) {
            winner = true;
        } else if(threeInRow(board[0][2], board[1][1], board[2][0])) {
            winner = true;
        } else {
            winner = false;
        }
        return winner;
    }
   
    /**
     * Determines whether the game is over
     * due to a draw.
     * Compares numMoves to the length.
     * @param board the tic-tac-toe game board
     * @return whether the game is over
     */
    public static boolean gameOverDraw(String board[][]) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j].equals("-")) {
                    return false;
                }
            }
        }
        return true;
    }
   
   
    public static void main(String[] args) {
        String board[][] = new String[3][3];
        String player = " ";
        String computer = "X";
        int row;
        int col;
        int numMoves = 0;
      
        System.out.println("Welcome to Tic-Tac-Toe!");
        Scanner input = new Scanner(System.in);
        System.out.print("\nWould you like to play as X or O: ");
        player = input.next().toUpperCase();
        if (player.equals("X")) {
            computer = "O";
        }
     
       initializeBoard(board);
       printBoard(board);
     
       while(!gameOverWinner(board) && !gameOverDraw(board)) {
            System.out.print("\nPlease enter your move:\nRow: ");
            row = input.nextInt();
            System.out.print("Column: ");
            col = input.nextInt();
            while (alreadyTaken(board, row, col)) {
                System.out.print("\nThat spot is already taken!"
                        + "\n\nPlease enter your move: \nRow:");
                row = input.nextInt();
                System.out.print("Column: ");
                col = input.nextInt();          

            }

            makePlacement(board, row, col, player);
            numMoves++;
            printBoard(board);
          
            if(gameOverWinner(board) || gameOverDraw(board)) {
                break;
            }
          
            row = randomPosition();
            col = randomPosition();
        
            while (alreadyTaken(board, row, col)) {  
                row = randomPosition();
                col = randomPosition();
            }
          
            makePlacement(board, row, col, computer);
            numMoves++;
            System.out.println("\nCounter move!");
          
            printBoard(board);
        }
        if(gameOverWinner(board)) {
            if (numMoves % 2 == 0) {
                System.out.println("\n" + computer + " wins!");
            } else {
                System.out.println("\n" + player + " wins!");
            }
        } else {
            System.out.println("\nIt's a tie!");
        }
        System.out.println("\n***Game Over***");
  
     
    }
}

Sample Output:

Welcome to Tic-Tac-Toe!

Would you like to play as X or O: X

Tic-Tac-Toe:
  1 2 3
1 - - -
2 - - -
3 - - -

Please enter your move:
Row: 2
Column: 2

Tic-Tac-Toe:
  1 2 3
1 - - -
2 - X -
3 - - -

Counter move!

Tic-Tac-Toe:
  1 2 3
1 - - -
2 - X -
3 - - O

Please enter your move:
Row: 3
Column: 1

Tic-Tac-Toe:
  1 2 3
1 - - -
2 - X -
3 X - O

Counter move!

Tic-Tac-Toe:
  1 2 3
1 O - -
2 - X -
3 X - O

Please enter your move:
Row: 1
Column: 3

Tic-Tac-Toe:
  1 2 3
1 O - X
2 - X -
3 X - O

X wins!

***Game Over***


2. Array Lists

  • When you use an ArrayList, you ask Java to manage an array for you.
  • An ArrayList can be very convenient, as all you will need to do is to call some ArrayList methods to interact with the array, rather than writing our own methods to do so.
  • Additionally, we will not need to know the exact length ahead of time, as we do with an array.
  • To begin our discussion on ArrayLists, let's review some of the challenges inherent in using an array to store data.

The Problems with Arrays

  • Arrays are a fundamental language construct in Java, used to store a collection of data (e.g. phone numbers, names in a class roster, etc).
  • However, the use of arrays presents some challenges.
Problem 1: Arrays are of fixed size:
    • But, what if I don't know ahead of time how many elements I will be storing in an array?
    • The most common approach is to make the array length longer than you think you will need.
String class_roster = new String[100];
    • However, this approach may not always be sufficient.
    • Consider a start up company that needs to store customer records. 
    • When the company first begins operations, will it be able to predict roughly how many customers it might acquire in the future?
    • Maybe not.
    • It might be expensive to allot more room for storage of customer data than it actually needs. However, it could be even more dangerous not to allot enough.

Illustration of an array as 10 boxes numbered 0 through 9; an index of 0 indicates the first element in the array

Arrays are of fixed size because all elements are stored next to each other in contiguous memory locations. Image Source

Problem 2: Maintaining an ordered list is "expensive" with arrays:
    • For example, let's say that I create an array to store my class roster.
    • I wait until the second week to insert each student name alphabetically into the array, thinking that I now have all the student names.
    • But, what if there is a late add?
    • What do I do about students who drop?
    • To maintain alphabetical order in either case will require me to shift array elements either up (removal) or down to create an empty space (insertion).
    • The process of shifting elements around inside of an array in order to insert or remove is "expensive" (potentially many steps to accomplish one action)
    • The below gif demonstrates insertion in a sorted array:
https://res.cloudinary.com/monkey-codes/image/upload/v1494831769/algorithms/array_insert_vjgpaz.gif

image source


Using an ArrayList instead of an Array
  • To avoid having to handle these two challenges directly, Java programmers often use an ArrayList rather than an array.
  • ArrayLists are simply arrays managed by Java.
  • With an ArrayList, you will not need to know the exact size of your data collection ahead of time.
    • When you declare an ArrayList variable, Java will automatically create an array of fixed length (10 elements).
    • When you run out of room inside this array, Java will create a new one and copy all of the original data into this new array for you.
    • All of these actions will occur automatically, without any extra lines of code or effort on your part.
  • Also, when you need to insert new data into or remove data from the ArrayList, Java will automatically shift the data around inside the ArrayList so that it can be inserted into the proper location or removed without leaving a hole inside the array.
  • All you will need to do is to call the appropriate methods.
  • It also offers several methods to search for a particular value in the an array.
  • Pretty convenient!
  • Let's look at how to use an ArrayList.
ArrayList Summary
ArrayList&#39;s have a default capacity of 10. You can call methods to get, set, add, and remove elements.

Declaring an ArrayList
  • Java offers several means to declare a new ArrayList variable
  • To declare an empty ArrayList, you will need to use the new keyword and also know the type of data you would like to store in the ArrayList:
ArrayList<String> names = new ArrayList<String>();

  • Note that the type of data to store goes in <> on both sides of the equals sign.
  • The general formula for declaring an ArrayList variable is as follows:
ArrayList<DataType> nameofArrayList = new ArrayList<DataType>();

  • Additionally, you can create an ArrayList from an already existing Collection.
  • Example converting from an array to an ArrayList and inserting into a new ArrayList:
String[] names = new String[3];
names[0] = "Xavier";
names[1] = "Xiao";
names[2] = "Xiuan";
ArrayList<String> names1 = new ArrayList<String>();

for (int i = 0; i < names.length; i++) {
    names1.add(names[i]);
}

ArrayList<String> names2 = new ArrayList<String>(names1);
  • To create an ArrayList from another ArrayList, all you need to do is to put the name of the ArrayList inside the parenthesis when you declare the new ArrayList variable.
  • All of the values from the ArrayList will be copied one-by-one into the new ArrayList.
  • Lastly, you can create an ArrayList of an exact predefined size by placing a number inside the parenthesis when you declare it.
ArrayList<String> names = new ArrayList<String>(3);
  • Note that if you decide you require a longer ArrayList at a later point in time, Java will still automatically create a new array for you and copy all of the data into the new, larger array.

A Word on Declaring ArrayList without a Type
  • Note also the use of the empty parenthesis when declaring an empty ArrayList.
  • Alternately, you are not required to indicate the datatype, but can instead declare the ArrayList using the following format:
ArrayList names = new ArrayList();
  • In this case, all data will be stored as a generic object type, not as their specific datatypes.
  • This is considered bad practice and should be avoided!

Accessing Data in the ArrayList: The get(index) Method
When calling get(), you pass the index of the element is a parameter and the method returns the value stored at that index

  • To access data in the array list, you call the get() method and pass it a specified index as an argument.
String first = names.get(0);
System.out.println("The second name is: " + names.get(1));


Inserting and Removing from an ArrayList: The add and remove methods
When an element is inserted into an ArrayList already at maximum capacity, all the elements are copied into a new ArrayList

  • To insert a new element in an array, you will need to call the add() method.
  • The add() method takes two parameters - the index number of where the element should be inserted, and the element itself.
names.add(2, "Xing"); //inserts "Xing" at index 2 in the ArrayList
  • If you wish simply to add the element to the very end of the array ("append" the element), you can call the add() method without specifying any index.
names.add("Zoe"); //inserts "Zoe" at the end of the ArrayList
  • If the array is already full and a new item needs to be inserted, Java will automatically create a new array and copy all of the old elements into it, along with the new element to insert.

  • To remove an element, you can call the remove() method. The remove() method requires that you specify the index number of the element to remove by passing it in as a parameter or the actual value to remove.

names.remove(1); //removes the element at index 1
                                 names.remove("Zoe"); //remove the element "Zoe"
  • Java will automatically copy up all of the elements in the array to cover over the hole left by removing the element.

Searching an ArrayList : The contains and indexOf Methods
The indexOf method returns the index number where the element is stored in the ArrayList

  • The ArrayList type offers several means of searching. You can search for an element with the view to returning its location, or simply with the view to discovering whether or not the element is stored inside of the ArrayList.
  • If you are only trying to determine whether a specific value is currently being stored inside the ArrayList, but do not care about its location, you can call the contains() method.
  • The contains() method returns a boolean to indicate whether or not the value is currently stored in the ArrayList.
boolean isStored = names.contains("Xing"); //Is "Xing" in the ArrayList?
  • The contains method requires that you place the value to search for inside of the parenthesis, when you call the method.
  • To determine the exact location of the element inside of the ArrayList, you would need to call the indexOf method.
  • The indexOf method will return an int, for the index number where the element is located.
  • It will return -1 if the element is not stored in the ArrayList.
int location = names.indexOf("Xing"); //returns index where "Xing" is stored or -1
  • Note that this method will return the first occurrence of the element inside the array (the first index number where it can be found).
  • If the element is stored at multiple indices, the indexOf method will only return the first occurrence.

Accessing the length of the ArrayList: the size Method
  • To access the length of an ArrayList, you call the size() method:
System.out.println(names.size());


Updating a value at an index in an ArrayList: the set Method
  • To update the value stored at an index in the underlying array, you can call the set method.
  • You will need to pass in the index number to update, as well as the new value you want stored at that index.
names.set(1, "Tam");

Additional ArrayList Methods
  • The ArrayList type offers many more methods than I have discussed above.
  • If you find there is something you would like to do with your ArrayList, the chances are good that there is a method that you can call to do it.
  • You can always consult the ArrayList documentation on the Oracle website.

Using ArrayLists as Method Parameters and Return Types
  • ArrayLists can be both parameters of methods and return types of methods
public static ArrayList<String> myMethod(ArrayList<String> a) {


Important Note (a Potential Downside of ArrayLists)!
  • ArrayLists cannot store primitive types
  • The types int, double, boolean, and char cannot be stored inside of an ArrayList
  • To store numbers, you can use two alternatives to int and double, known as Integer and Double.
  • For characters use Character, instead of char, and for booleans, use type Boolean.
  • These types are objects, meaning they have methods that can be called on them.
  • However, they still store data of the same type as int, double, char, and boolean.
Not allowed:

ArrayList<int> scores = new ArrayList<int>(); //NOT ALLOWED!

Instead use:

ArrayList<Integer> scores = new ArrayList<Integer>(); //correct!

Not allowed:

ArrayList<double> temperatures = new ArrayList<double>(); //NOT ALLOWED!

Instead use:

ArrayList<Double> temperatures = new ArrayList<Double>(); //correct!


ArrayList Example
  • Below is an example program using ArrayLists:
import java.util.ArrayList;
import java.util.Scanner;

public class ArrayListPractice {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<String>();
        int numNames = 3;
        Scanner input = new Scanner(System.in);
        System.out.println("Enter " + numNames + " names: ");
        for (int i = 0; i < numNames; i++) {
            names.add(input.next());
        }
       
        System.out.println(names);
       
    }
}
  • Note that the ArrayList can simply be printed using System.out.println(), without writing a separate method or using a for loop to print the elements one-by-one as required when using an array.
  • The ArrayList type has a designated style for printing using [] and , to separate the elements.
  • Note also that you must import java.util.ArrayList; to be able to use an ArrayList in your program.

Activity 5.2: Practice with ArrayLists (10 pts)

  • Open up Eclipse and create a new class called ArrayListPractice.java
  • Next, copy and paste the below program into your file and run the code.
  • Note that this is a variation on a program you wrote in CIS 36A if you took the class from me.
  • Your job is to take the given code, remove all the arrays and replace them with the identical ArrayLists. There should be no arrays in your program.
  • You will need to call the ArrayList methods as defined in the lesson notes above.
  • Note that you will not be able to do method overloading with ArrayLists so you should assign different names to your methods.
  • Once you have made the changes, you should get identical output as the given version of the program.
  • Submit your program to Canvas when you are finished.
/**
 * @author
 * CIS 36B
 * Activity 5.2
 */

import java.util.ArrayList;
import java.util.Scanner;

public class ArrayListPractice {
    public static void main(String[] args) {
       
        int scores[] = {95, 96, 97, 98, 99};
        System.out.println("Integer exam scores:");
        print(scores);
        System.out.println();
       
        System.out.println("After adding extra credit:");
        addExtraCredit(scores);
        print(scores);
        System.out.println();
       
        double  rainfall[] = {23.4, 16.4, 18.9, 52.7};
        System.out.println("Rainfall in Inches:");
        print(rainfall);
        System.out.println();
       
        String vowels[] = {"a", "e", "i", "o", "u"};
        System.out.println("Vowels in the Latin Alphabet:");
        print(vowels);
        System.out.println();
    }
    /**
     * Prints an array of integer values
     * @param values the array of ints
     */
    public static void print(int values[]) {
        for (int i = 0; i < values.length - 1; i++) {
            System.out.print(values[i] + ", ");
        }
        System.out.println(values[values.length-1]);
    }
   
    /**
     * Prints an array of double values
     * @param values the array of doubles
     */
    public static void print(double values[]) {
        for (int i = 0; i < values.length - 1; i++) {
            System.out.print(values[i] + ", ");
        }
        System.out.println(values[values.length-1]);
    }
   
    /**
     * Prints an array of String values
     * @param values the array of Strings
     */
    public static void print(String values[]) {
        for (int i = 0; i < values.length - 1; i++) {
            System.out.print(values[i] + ", ");
        }
        System.out.println(values[values.length-1]);
    }
   
    /**
     * Add 5 to each element in an integer array
     * @param values the array of ints
     */
    public static void addExtraCredit(int values[]) {
        for(int i = 0; i < values.length; i++) {
            values[i]+=5;
        }
    }

}

Your Program Should Give the Identical Output to the Output Below:

Integer exam scores:
95, 96, 97, 98, 99

After adding extra credit:
100, 101, 102, 103, 104

Rainfall in Inches:
23.4, 16.4, 18.9, 52.7

Vowels in the Latin Alphabet:
a, e, i, o, u

Wrap Up: 

  • Answer the practice exam questions for this lesson on Canvas


Upcoming Assignments:

  • Activities 5.1 and 5.2 due Tuesday at 11:59pm
  • Lesson 5 Practice Exam Questions due Tuesday at 11:59pm
  • Quiz 3 due Friday at 11:59pm
  • Lab 3 due Monday at 11:59pm

~ Have a Great Day! ~