Arrays and ArrayLists
Objectives:
• Learn about arrays and when to use them
• Learn the syntax for declaring and initializing
arrays and how to access array’s size and
elements
• Learn about the [Link] class
• Discuss “for each” loops
• Learn simple array algorithms
• Understand two-dimensional arrays
What is an Array
• An array is a block of consecutive memory
locations that hold values of the same data
type.
• Individual locations are called array’s
elements.
• When we say “element” we often mean the
value stored in that element.
1.39 1.69 1.74 0.0 An array of
doubles
What is an Array (cont’d)
• Rather than treating each element as a
separate named variable, the whole array
gets one name.
• Specific array elements are referred to by
using array’s name and the element’s
number, called index or subscript.
1.39 1.69 1.74 0.0
c[0] c[1] c[2] c[3] c is array’s
name
Indices (Subscripts)
• In Java, an index is written within square
brackets following array’s name (for
example, a[k]).
• Indices start from 0; the first element of an
array a is referred to as a[0] and the n-th
element as a[n-1].
• An index can have any int value from 0 to
array’s length - 1.
Indices (cont’d)
• We can use as an index an int variable or any
expression that evaluates to an int value. For
example:
a [3]
a [k]
a [k - 2]
a [ (int) (6 * [Link]()) ]
Indices (cont’d)
• In Java, an array is declared with fixed
length that cannot be changed.
• Java interpreter checks the values of
indices at run time and throws
ArrayIndexOutOfBoundsException if an
index is negative or if it is greater than the
length of the array - 1.
Why Do We Need Arrays?
• The power of arrays comes from the fact that
the value of a subscript can be computed and
updated at run time.
No arrays: With arrays:
int sum = 0; int n = 1000;
sum += score0; int sum = 0, k;
1000 sum += score1;
times! … for (k = 0; k < n; k++)
sum += score999; sum += scores[k];
Why Arrays? (cont’d)
• Arrays give direct access to any element —
no need to scan the array.
No arrays: With arrays:
if (k == 0) display (scores[k]);
1000 display (score0);
times! else if (k == 1)
display (score1);
else
… // etc.
Arrays as Objects
• In Java, an array is an object. If the type of
its elements is anyType, the type of the array
object is anyType[ ].
• Array declaration: anyType [ ] arrName;
• Declaring and Allocating arrays
Arrays are objects that occupy memory
Allocated dynamically with operator new
int c[] = new int[ 12 ];
– Equivalent to
int c[]; // declare array
c = new int[ 12 ]; // allocate array
• We can allocate arrays of objects too
String b[] = new String[ 100 ];
Arrays as Objects (cont’d)
• As with other objects, the declaration creates
only a reference, initially set to null. An array
must be created before it can be used.
• One way to create an array:
arrName = new anyType [length] ; Brackets,
not parens!
Declaration and Initialization
• When an array is created, space is allocated
to hold its elements. If a list of values is not
given, the elements get the default values.
For example:
length 10,
all values
scores = new int [10] ; set to 0
words = new String [10000]; length 10000,
all values set to
null
Initialization (cont’d)
• An array can be declared an initialized in one
statement. For example:
int [ ] scores = new int [10] ;
private double [ ] gasPrices = { 3.05, 3.17, 3.59 };
String [ ] words = new String [10000];
String [ ] cities = {"Atlanta", "Boston", "Cincinnati" };
Initialization (cont’d)
• Otherwise, initialization can be postponed
until later. For example:
Not yet
String [ ] words; initialized
...
words = new String [ [Link]() ];
Not yet
private double[ ] gasPrices; initialized
…
gasPrices = new double[ ] { 3.05, 3.17, 3.59 };
Array’s Length
• The length of an array is determined when
that array is created.
• The length is either given explicitly or comes
from the length of the {…} initialization list.
• The length of an array arrName is referred to
in the code as [Link].
• length is like a public field (not a method) in
an array object.
Initializing Elements
• Unless specific values are given in a {…} list,
all the elements are initialized to the default
value: 0 for numbers, false for booleans, null
for objects.
• If its elements are objects, the array holds
references to objects, which are initially set to
null.
• Each object-type element must be initialized
before it is used.
Initializing Elements (cont’d)
• Example:
Array not
Color[ ] pens; created yet
... Array is created;
pens = new Color [ 3 ]; all three elements
are set to null
...
pens [0] = [Link];
pens [1] = new Color (15, 255, 255); Now all three
pens [2] = [Link](); elements are
initialized
Passing Arrays to Methods
• As other objects, an array is passed to a
method as a reference.
• The elements of the original array are not
copied and are accessible in the method’s
code.
// Swaps a [ i ] and a [ j ]
public void swap (int [ ] a, int i, int j)
{
int temp = a [ i ];
a [ i ] = a [ j ];
a [ j ] = temp;
}
Returning Arrays from
Methods
• As any object, an array can be returned from
a method.
• The returned array is usually constructed
within the method or obtained from calls to
other methods.
• The return type of a method that returns an
array with someType elements is designated
as someType[ ].
Returning Arrays from
Methods (cont’d)
public double[ ] solveQuadratic
(double a, double b, double c)
{
double d = b * b - 4 * a * c;
if (d < 0) return null;
Or simply:
d = [Link](d);
return new double[ ]
double[ ] roots = new double[2]; { (-b - d) / (2*a),
roots[0] = (-b - d) / (2*a); (-b + d) / (2*a) };
roots[1] = (-b + d) / (2*a);
return roots;
}
[Link]<E>
• Implements a list using an array.
• Can only hold objects (of a specified type),
not elements of primitive data types.
• Keeps track of the list capacity (the length of
the allocated array) and list size (the number
of elements currently in the list)
capacity
size
"Cat" "Hat" "Bat"
...
ArrayList Generics
• Starting with Java 5, ArrayList and other
collection classes hold objects of a specified
data type.
• The elements’ data type is shown in angle
brackets and becomes part of the ArrayList
type. For example:
ArrayList<String> words = new ArrayList<String>();
ArrayList<Integer> nums = new ArrayList<Integer>();
ArrayList<E> Constructors
Java docs use the letter E as
the type parameter for elements
in generic collections
ArrayList<E> ( ) Creates an empty
ArrayList<E> of
default capacity (ten)
ArrayList<E> (int capacity)
Creates an empty
ArrayList<E> of the
specified capacity
ArrayList<E> Methods
(a Subset)
int size()
boolean isEmpty ()
boolean add (E obj) returns true
void add (int i, E obj) inserts obj as the
i-th value; i must
E set(int i, E obj) be from 0 to size()
E get(int i)
i must be from 0 to
E remove(int i) size() -1
boolean contains(E obj) use equals to
int indexOf(E obj) compare objects
ArrayList Example
ArrayList<String> names =
new ArrayList<String>( );
[Link]("Ben");
[Link]("Cat");
[Link](0, "Amy");
[Link](names);
Output
ArrayList’s toString
method returns a string of
[Amy, Ben, Cat] all the elements, separated
by commas, within [ ].
ArrayList<E> Details
• Automatically increases (doubles) the capacity
when the list runs out of space (allocates a
bigger array and copies all the values into it).
• get(i) and set(i, obj) are efficient because an
array provides random access to its elements.
• Throws IndexOutOfBoundsException when
i < 0 or i size()
(or i > size() in add (i, obj) )
ArrayList Pitfalls
// Remove all occurences
// of "like" from words: Caution: when you remove
elements, a simple for loop
int i = 0; doesn’t work:
while (i < [Link]()) for (int i = 0; i < [Link]();
{ i+
if ("like".equals([Link](i)) +)
[Link](i); {
else if ("like".equals([Link](i))
i++; [Link](i);
} }
Shifts all the
elements after the i-th
to the left and
decrements the size
“For Each” Loop
• Introduced in Java 5
• Works both with standard arrays and
ArrayLists
• Convenient for traversing
“For Each” Loop: Example 1
int [ ] scores = { ... };
...
int sum = 0;
for (int s : scores)
{
sum += s;
Basically the same as:
}
...
for (int i = 0;
i < [Link]; i++)
{
int s = scores[i];
sum += s;
}
“For Each” Loop: Example 2
ArrayList<String> words = new ArrayList<String>();
...
for (String str : words)
{
[Link](str); // process str
}
Basically the same as:
for (int i = 0;
i < [Link](); i++)
{
String str = [Link](i);
[Link](str);
}
Inserting a Value into
a Sorted Array
• Given: an array, sorted in ascending order.
The number of values stored in the array is
smaller than array’s length: there are some
unused elements at the end.
• Task: insert a value while preserving the
order.
Inserting a Value (cont’d)
1. Find the right place to insert:
5 Can be combined
1 1 2 3 8 13 together in one
loop: look for the
2. Shift elements to the right, place to insert
starting from the last one: while shifting.
5
1 1 2 3 8 13
3. Insert the value in its proper place:
1 1 2 3 5 8 13
Inserting a Value (cont’d)
// Returns true if inserted successfully, false otherwise
public boolean insert(double[ ] arr, int count, double value)
{
if (count >= [Link])
return false;
int k = count - 1;
while ( k >= 0 && arr [ k ] > value )
{
arr [ k + 1 ] = arr [ k ];
k--;
}
arr [ k + 1] = value;
return true;
}
Lab: Index Maker
[Link] [Link]
One fish A 12, 14, 15
Two fish ARE 16
Red fish BLACK 6
Blue fish. BLUE 4, 7
CAR 14
Black fish FISH 1, 2, 3, 4, 6, 7, 8, 9, 16
Blue fish HAS 11, 14
Old fish LITTLE 12, 14
New fish. LOT 15
NEW 9
This one has OF 16
a little star. OLD 8
ONE 1, 11, 14
This one has a little car. RED 3
Say! What a lot SAY 15
of fish there are. STAR 12
THERE 16
THIS 11, 14
TWO 2
WHAT 15
Two-Dimensional Arrays
• 2-D arrays are used to represent tables,
matrices, game boards, images, etc.
• An element of a 2-D array is addressed using
a pair of indices, “row” and “column.” For
example:
board [ r ] [ c ] = 'x';
2-D Arrays: Declaration
// 2-D array of char with 5 rows, 7 cols:
char[ ] [ ] letterGrid = new char [5][7];
// 2-D array of Color with 1024 rows, 768 cols:
Color[ ] [ ] image = new Color [1024][768];
// 2-D array of double with 2 rows and 3 cols:
double [ ] [ ] sample =
{ { 0.0, 0.1, 0.2 },
{ 1.0, 1.1, 1.2 } };
2-D Arrays: Dimensions
• In Java, a 2-D array is basically a 1-D array of
1-D arrays, its rows. Each row is stored in a
separate block of consecutive memory
locations.
• If m is a 2-D array, then m[k] is a 1-D array,
the k-th row.
• [Link] is the number of rows.
• m[k].length is the length of the k-th row.
Dimensions (cont’d)
• Java allows “ragged” arrays, in which different
rows have different lengths.
• In a rectangular array, m[0].length can be
used to represent the number of columns.
“Ragged” array: Rectangular array:
[Link] [Link]
m[3].length m[0].length
2-D Arrays and Nested Loops
• A 2-D array can be traversed using nested loops:
for (int r = 0; r < [Link]; r++)
{
for (int c = 0; c < m[0].length; c++)
{
... // process m[ r ][ c ]
}
}
“Triangular” Loops
• “Transpose a matrix” idiom:
int n = [Link];
for (int r = 1; r < n; r++)
{
The total number of
for (int c = 0; c < r; c++) iterations through the
{ inner loop is:
double temp = m [ r ][ c ];
m [ r ][ c ] = m [ c ][ r ]; 1 + 2 + 3 + ... + n-1 =
m [ c ][ r ] = temp; n (n - 1) / 2
}
}