Transcript Arrays and Array Lists

Arrays and Array Lists
CS 21a
Problem 1:
Reversing Input


Problem: Read in three
numbers and then print
out the numbers in
reverse order
Straightforward Java
application



public static void main( String[] args )
throws IOException
{
String temp;
double num1, num2, num3;
temp
num1
temp
num2
temp
num3
declare three variables of
type double
read in String values for
each of them and convert
print them out starting
with the last variable read
in
}
=
=
=
=
=
=
console.readLine();
Double.parseDouble(temp);
cosole.readLine();
Double.parseDouble(temp);
console.readLine();
Double.parseDouble(temp);
System.out.println( num3 );
System.out.println( num2 );
System.out.println( num1 );
Generalizing a Program


Suppose we wanted the same program
but wanted 10 instead of 3 numbers?
Suppose we wanted to read in 1000
numbers?


More than 3000 lines of code if we used the
same approach!
Solution: arrays
Arrays

pronounced “ar-ray”, w/ stress on 2nd syllable

Definition



collection of elements of the same type
each element is accessed through an index
In Java,



declaration:
creation:
use:

double[] nums;
nums = new double[8];
nums[3] = 6.6;
Note: starting index is 0 (0 to 7, above)
double nums[]
is also legal, but
double[] nums
is preferred, since it
emphasizes that the
type is double[]
(“double array” or
“array of doubles”)
Visualizing an Array
nums
null
Declare:
double[] nums;
Visualizing an Array
nums
null
Declare:
double[] nums;
Create:
nums = new double[8];
0
0.0
1
0.0
2
0.0
3
0.0
4
0.0
5
0.0
6
0.0
7
0.0
Visualizing an Array
nums
Declare:
double[] nums;
Create:
nums = new double[8];
Use:
nums[3] = 6.6;
0
0.0
1
0.0
2
0.0
3
0.0
6.6
4
0.0
5
0.0
6
0.0
7
0.0
Reversing 10 numbers

Use arrays and loops




declare
double[] nums
create
new double[10]
use a for-statement to
read in the numbers
use a for-statement to
print them out in
reverse
public static void main( String[] args )
throws IOException
{
double[] nums = new double[10];
for ( int i = 0; i < 10; i++ )
{
String temp = console.readLine();
nums[i] = Double.parseDouble(temp);
}
}
for ( int i = 9; i >= 0; i-- )
{
System.out.println( nums[i] );
}
Scaling up

What if you want to
change the number
of elements?


public static void main( String[] args )
throws IOException
{
double[] nums = new double[10];
for ( int i = 0; i < 10; i++ )
{
String temp = console.readLine();
nums[i] = Double.parseDouble(temp);
}
would have to find
and change all places
using 10 (including
the 9 in the for loop)
very tedious and
error-prone
}
for ( int i = 9; i >= 0; i-- )
{
System.out.println( nums[i] );
}
Using Constants

What if you want to
change the number
of elements?



would have to find
and change all places
using 10 (including
the 9 in the for loop)
very tedious and
error-prone
public class ReverseArray
{
…
public static final int MAX = 10;
public static void main( String[] args )
throws IOException
{
double[] nums = new double[MAX];
for ( int i = 0; i < MAX; i++ )
{
String temp = console.readLine();
nums[i] = Double.parseDouble(temp);
}
Solution: use a
constant
}
for ( int i = MAX - 1; i >= 0; i-- )
{
System.out.println( nums[i] );
}
Using Constants


A constant has to be a
class-wide variable
(not a local variable)
Important keywords



static -- means value is
shared by all instances
(more later)
final -- means value can’t
be changed (i.e., it’s a
constant)
public class ReverseArray
{
…
public static final int MAX = 10;
public static void main( String[] args )
throws IOException
{
double[] nums = new double[MAX];
for ( int i = 0; i < MAX; i++ )
{
String temp = console.readLine();
nums[i] = Double.parseDouble(temp);
}
Capitalization

ALL_CAPS, words
separated by underscore
}
for ( int i = MAX - 1; i >= 0; i-- )
{
System.out.println( nums[i] );
}
Constants and “Magic Numbers”

Constants are useful for “magic numbers” – i.e.,
specific values that are used throughout the code


e.g., MAX_LENGTH, SCREEN_WIDTH, PI, BLUE,
DASHED_LINE, etc.
Useful because

makes code more readable and maintainable


e.g., WHITE is easier to understand and easier to remember
than 255
makes modifications easier

e.g., in reversing program example, we just need to change
MAX. No need to look for 10 and 9 and change them.
Problem 2: Collection of Objects

How can we write Bank so it can handle a larger
number of BankAccounts?

Right now, we can only handle a small number of
accounts (2 or 3)
withdraw( “Alice”,
“1234”, 200 )
getBalance( “Bob”,
“4321” )
Solution: Array of Objects

Declaration


Creation of the Array




BankAccount[] accounts;
accounts = new BankAccount[5];
creates an array of references to BankAccounts
but no actual BankAccounts yet
Creation of Objects


for ( i = 0; i < 5; i++ )
{ accounts[i] = new BankAccount();
}
creates the BankAccounts themselves and assigns
these to the references
Visualizing an Array of Objects
accounts
null
Declare:
BankAccount[] accounts;
Visualizing an Array of Objects
BankAccount-type references
accounts
null
Declare:
BankAccount[] accounts;
Create array: accounts =
new BankAccount[5];
0
null
1
null
2
null
3
null
4
null
Visualizing an Array of Objects
BankAccount-type references
acounts
null
Declare:
BankAccount[] accounts;
Create array: accounts =
new BankAccount[5];
Create objects:
for ( i = 0; i < 5; i++ )
{ accounts[i] = new BankAccount(i * 10);
}
0
null
1
null
2
null
3
null
4
null
BankAccount
balance
0
BankAccount
balance
10
BankAccount
balance
20
BankAccount
balance
30
BankAccount
balance
40
Visualizing an Array of Objects
BankAccount-type references
acounts
null
Declare:
BankAccount[] accounts;
Create array: accounts =
new BankAccount[5];
Create objects:
for ( i = 0; i < 5; i++ )
{ accounts[i] = new BankAccount(i * 10);
}
Use objects: e.g., accounts[3].getBalance();
0
null
1
null
2
null
3
null
4
null
BankAccount
balance
0
BankAccount
balance
10
BankAccount
balance
20
BankAccount
balance
30
(returns 30)
BankAccount
balance
40
Approach

Include a name field in BankAccount

Create set and get methods for this field

Declare an array of BankAccount objects

Use a loop in the findAccount() method of
Bank
Approach



A field representing the
acct name has been
added: acctName
public class BankAccount
{
private double balance;
private String acctName;
Constructor has been
modified to accept an
initial balance
Set and get methods
were created to access
acctName
}
public BankAccount( double initBalance )
{
balance = initBalance;
}
public void setAcctName( String name )
{
acctName = name;
}
public String getAcctName()
{
return acctName;
}
…
Approach



A field representing an array
of BankAccounts was added:
accounts
public class Bank
{
private BankAccount[] accounts;
private static final int MAX = 10;
There is also a constant
representing the maximum
amount of bankAccounts
bank can handle: MAX
The array is initialized in the
constructor. It is also
populated with 2
BankAccount objects named
“john” and “marsha”
…
}
public Bank()
{
accounts = new BankAccount[MAX];
accounts[0] = new BankAccount(100);
accounts[0].setAcctName(“john”);
accounts[1] = new BankAccount(200);
accounts[1].setAcctName(“marsha”);
}
Approach


findAccount
contains a forstatement that
searches for
the appropriate
account
The getName()
method of an
account is used
to get the
name and
compare it with
the name
parameter
public class Bank
{
…
private BankAccount findAccount( String name )
{
for( int x = 0; x < MAX; x++ )
{
if( accounts[x].getAcctName().equals(name) )
{
return accounts[x];
}
}
Be careful when writing code
return null;
like this. Doing this gives a
}
NullPointerException if no
…
BankAccount instance is
}
assigned to that location.
Approach


public class Bank
{
…
A reference to the
private BankAccount findAccount( String name )
correct account is
returned when it is {
for(int x = 0; x < MAX; x++)
found, otherwise
{
the value returned
if ( accounts[x] != null )
is null
{
if( accounts[x].getAcctName().equals(name) )
A return statement
{
is put inside the
return accounts[x];
for-statement to
}
“break out” of the
}
loop when the
One possible alternative as
}
correct account has
this first checks if the
return null;
been found
location contains an instance
}
of BankAccount (i.e., not null)
…
}
Approach
public class Bank
{
…
private BankAccount findAccount( String name )
{
for(int x = 0; x < numAccounts; x++)
{
if( accounts[x].getAcctName().equals(name) )
{
return accounts[x];
}
}
Another possible alternative
return null;
is to change the limit of x to
}
the actual number of accounts
…
the array contains.
}
Approach

What is the value of numAccounts?
public class Bank
{
private BankAccount[] accounts;
private static final int MAX = 10;
private int numAccounts = 0;
…
}
public Bank()
{
accounts = new BankAccount[MAX];
accounts[0] = new BankAccount(100);
accounts[0].setAcctName(“john”);
accounts[1] = new BankAccount(200);
accounts[1].setAcctName(“marsha”);
numAccounts = 2;
}
Creating new BankAccounts
public void openAccount( String name, int initbal )
{
if ( numAccounts < MAX )
{
accounts[numAccounts] = new BankAccount( initbal );
accounts[numAccounts].setAcctName( name );
numAccounts++;
}
else
{
System.out.println( "Maximum number of accounts reached" );
}
}
Using openAccount as a
convenience method

In the Bank’s constructor:
public Bank()
{
accounts = new BankAccount[MAX];
}
openAccount( "john", 1000 );
openAccount( "marsha", 2000 );
More About Arrays

Arrays are objects




the array variable is just a reference to the actual array
that contains the values
need to use “new” after declaring
passed as a reference when used as method parameter
Special features

a public final int length field returns the array size


in recent example, accounts.length would return 10
[] operator only work with arrays
More About Arrays

ArrayIndexOutOfBounds exception



valid indices for array of size n: 0 to n-1
any access to other indices causes an error
Array size can’t be changed after array is created

To expand array, we need to create a new array, copy
old array contents, then point array variable to new
array
Array Initializers



You can initialize an array with the
following syntax:
String[] responses = { “Hello”, “Hi”,
“How are you”, “How do you do” };
Can be used for fields, local variables, and
even constants
Useful Pattern

Put different responses for different cases in an
array


Assign an integer to represent different cases


String[] responses = { “Hello”, “Hi”,
“How are you”, “How do you do” };
In this case 0 means the program will say “Hello”, 1
means it will say “Hi”, etc.
Now you can generate the data for each case
accordingly


e.g., What does the following code do?
int greetingCase = Math.random() * responses.length;
String greeting = responses[greetingCase] + “World”;
System.out.println( greeting );
Multi-dimensional Arrays (Optional)

A natural extension of simple (1D) arrays



2D declaration: char[][] grid;
think “array of arrays”
Array creation
grid = new char[10][20]; // 10 rows, 20 columns

Another way
grid = new char[10][];
// creates array of 10 char[]’s
for (i = 0; i < 10; i++)
{ grid[i] = new char[20]; // creates a size-20 array
}
 This way allows for varying row sizes
Visualizing 2D Arrays
char[]-type references
char[][]
0
null
Declare:
1
2
char[][] grid;
Create array of rows:grid = new char[5][];
Create rows:
for ( i = 0; i < 5; i++ )
{ grid[i] = new char[3];
}
Use objects: e.g., grid[3][2] = ‘C’
3
4
C
Using 2D Arrays

To refer to individual element, use two indices


Using only one index refers to a single
dimensional array



e.g., grid[2][1] = ‘X’;
e.g., grid[4] refers to row 4
grid[4].length is the length of row 4 (in this case, it’s
3)
The array variable by itself refers to the top-level
array (i.e., the array of rows)

grid.length is the length of the array of rows (i.e., it’s
the number of rows)
Problem 3, Flexible collections

How can we write Bank so it can have an arbitrary
number of BankAccounts?

Right now, we can only handle a small and fixed number
of accounts (2 or 3)
withdraw( “Alice”,
“1234”, 200 )
getBalance( “Bob”,
“4321” )
The Java Collections Framework



A set of classes that you can use for
containing arbitrarily large collections of
objects
To use, you must say
import java.util.*;
at the top of your code
Some basic Collections classes


ArrayList, Vector
HashMap, Hashtable
ArrayList

ArrayList<String> names
Indexed list of objects that
automatically resizes


The list is ordered, with each
object in the list having an index,
from 0 to n-1
Most commonly used methods





boolean add( E element )
int size()
E get( int index )
E set( int index, E element )
plus others (see API docs)
ArrayList
0
“Bart”
1
“Lisa”
2
“Maggie”
Note: ArrayLists in Java 5 is used slightly
differently from its previous versions.
ArrayList Example
import java.util.*;
ArrayList<String>
public class ArrayListDemo1
You have to specify
{
the type of object
public void execute()
it has to store.
{
ArrayList<String> names
= new ArrayList<String>();
names.add( "Bart" );
ArrayList
names.add( "Lisa" );
names.add( "Maggie" );
0
for ( int i = 0; i < names.size(); i++ )
{
1
System.out.println( names.get( i ) );
}
2
names.set( 1, "Homer" );
names.add( "Marge" );
3
for ( int i = 0; i < names.size(); i++ )
{
System.out.println( names.get( i ) );
}
}
}
names
“Bart”
“Homer”
“Lisa”
“Maggie”
“Marge”
Using Other Types
ArrayList accts
import java.util.*;
public class ArrayListDemoWithBankAccounts
{
public void execute()
{
ArrayList<BankAccount> accts
= new ArrayList<BankAccount>();
accts.add( new BankAccount( 2000 ) );
accts.get(0).setAcctName(“Alice”);
accts.add( new BankAccount( 1000 ) );
accts.get(1).setAcctName(“Bob”));
for ( int i = 0; i < accts.size(); i++ )
{
BankAccount curAccount = accts.get( i );
BankAccount
int balance
ArrayList
}
}
String name
“Alice”
0
1
System.out.println(
"Bank Account #" + i
+ "Owner: " + curAccount.getAcctName() + ", "
+ "Balance: " + curAccount.getBalance() );
}
2000
BankAccount
int balance
1000
String name
“Bob”
Looping through ArrayLists

Using an index …
for ( int i = 0; i < accts.size(); i++ )
{
BankAccount curAccount = accts.get( i );
System.out.println( … );
}

Using an “enhanced for” …
for ( BankAccount b : accts )
{
System.out.println( b.getBalance() );
Simpler than a regular for loop. All you have to specify
}
is the object (BankAccount) and the ArrayList (accts).
Exercises

Modify the Bank class, add a
createAccount() method that adds
another BankAccount object for the Bank
to manage.


First, do this using an array (accounts).
Then, convert Bank from arrays to ArrayLists.