An array is a data structure
used to implement a list object, where the elements in the list are the
same type; for example, a class list of 25 test scores, a membership
list of 100 names, or a store inventory of 500 items. For an array of N elements in java, index values ("subscripts") go from 0 to N  1. Individual elemnts are accessed as follows: If arr is the name of the array, the elements are arr (0), arr (1),...,arr (N1). If a negative subcript is used, or a subcript k where kN, an Array index out of bounds exeption is thrown. 

Initialization 
In Java, an array is an object,
therefore, the keyword new must be used in its creation. The size of an
array remains fixed once it has been created. As with String objects,
however, an array reference may be ressigned to a new array of a
different size. 

ExampleAll of the following are equivalent. each creates an array of 25 double values and assigns the reference data to this array.1. double ( ) data = new double (25); 2. double data ( ) = new double (25); 3. double data ( ); data = new double (25); A subsequent statement like data = new double (40) reassigns data to a new array of length 40. The memory allocated for the previous data array is recycled by Java's automatic garbage callection system. When arrays are declared, the elemnts are automatically initialized to zero for the primitive numeric data types ( int and double), to false for boolean variables, or to null for object references. It is possible to declare several in a single statement. For example, int ( 0 intList1, intList2; //declares intList 1 and intList2 to int ( ) arr1 = // contain int values new int (15), arr2 = new int (30); //reserves 15 slots // for arr1, 30 for arr2 

Initializer ListSmall arrays whose values are known can be declared with an intializer list. For example, instead of writing int ( ) coins = int (4) coins (0) = 1; coins (1) = 5; coins (2) = 10; coins (3) = 25; you can write int ( ) coins = {1, 5, 10,25 }; This construction is the one case where new is not required to create an array. 

Length of Array 
A Java array has a final
public intance variable ( i.e., a constant) lenght which can be
accessed when you need the number of elements in the array. For example, String ( ) names = new String (25) ; <code to iinitialize names> //loop to process all names in array for (int i=0; <nmes. length; i++) <process names> 

Note 
String s = "Confusing syntax!", int size + s. length ( ) ; // assigs 17 to size 

Arrays as Parameters 
Since arrays are treated as objects, passing an array as a paramater means passing its object reference. No copy is made of the array. thus the elements of the actual array can be accessed and modifield. Example 1 Array elemets accessed but not modified: // return index of smallest elements in array arr of integers public static int finMin ( int[] arr) int min = arra[0] ; int minIndex = 0; for (int i = 1 i< arr. length; i ++ ) if (arr [i] , min) // found a smaller element minIndex = i ; return minIndex; To call this meyhod ( in the same class that it;s defined): int [] array; < code to initialize array> int min = finMin ( array) ; 

Note 
Example 2 Array elements modifield: //Add 3 to each element of array b public static void changedArray ( int [] b ) for (int i = 0; i <b. length; i ++) b [ i ] += 3; To call this method 9 in the same class): int [] list = {1,2,3,4 } chargeArray 9 list); System. out print (" The charged list id " ) fot ( int i=0; i<list. length; i==) Syatem. out.print ( list [i] = " " ) ; The output produced is The changed list is 4 5 6 7 Look at the the memory slots to see how this happens: 

Example 3 Contrast the changeArray method with the following attempt to modify one array element: //Add 3 to an element puclic static void chageElement (int n) n+ = 3; Here is some code that invokes this method: int [] list = {1, 2, 3, 4} System. out.print ("Original array: ") for (int i=o; i <list. length; i ++) System. out. print (list[] + "" ); changeElement ( list [i] = " " ); System.out.print9"/nModified array: " ); for (int i=0 ; i <list.length; i ++) System.out.print (list[i] + " " ); Contrary to the programmers's expectation, the output is Original array: 1 2 3 4 Modified array: 1 2 3 4 A look at the memory slots shows why the list remains unchanged.
The point of this is that primitive types including single array elemnts of type int or double are passed by value. A copy is made of the actual perameter, and the copy is erased on exiting the method. 

Example 4 // Swap arr [i] and arr [j] in array public static void swap 9int [] arr, int i, int j) int temp = arra[i]; arra [j] = arr [j]; arra [j] = temp ; To call the swap method: int[] list = { 1, 2, 3, 4} ; swap 9list, 0, 3 ) ; System. out.print ("The changed list is: " ) ; for (int i=0; i< list.length; i ++) System.out.print (list [i] + " " ) The out put shows that the program worked as intended The changed list is : 4 2 3 1 

Note 
Don't make the same mistake as
in Example 3. The following will not work: public static void swap (int i, int j) inr temp = i; i = j; j = temp; int[] loist = { 1, 2, 3, 4 }; swap (list [0], list [3] ; // oops! list won't change 

Example 5 Here are two different approaches for reading numbers into an array. Approach 1 //Precondition: array arr declared with NUM_ELEMENTS slots //Postcondition: elements of array read from the keyboard public static void getIntegers 9int [] arr) for (int i = 0; i <arr. legth; i ++) System. outprintln 9"Enter integer:" ); arr [i] = I0. reading (); // read user input To call this method: int [] list = new int {NUM_ELEMTS]; getIntegers (list); 

Note 
The method getIntergers
modifies the array that is passed top it. Approach 2 Let the return type of the method be an array (actually, a reference to an array). //Precondition: array undefined //Postcondition: returns array containing NUM_ELEMENTS integers // read from the keyboard public static int [] getIntegers 90 int [] arr = new int [ NUM_ELEMENTS]; for 9 int i = 0; i <arr. length; i ++) System.out.printin ("Enter integer: " ) ; arr[i] = I0.eadInt (); //read user input return arr; To call this method: int [] list getIntgers90; 

Note 
The following sequence of
calling statements would not be wrong: int [] list = new int [NUM_ELEMENTS]; llist = getIntegers () ; It is, however; unnecessary since the getIntegers method creates a new array. It's not wrong to use new twice for the same array, but it's inefficient. 

Array Variables in a Class 
Consider a simple Deck
class in which a deck of cards is represented by the integers o to 51. public class Deck Private int [] myDeck private static random r; // random number generator public final static in NUMCARDS = 52; // constructor public Deck() myDeck = new int [NUMCARDS] ; for 9 int i = 0; i<NUMCARDS; i ++) myDeck [i] = i; //write contents of Deck public void writeDeck () for ( int i  0; i<NUMCARDS; i ++) System.out.print (myDeck[i] + " " ); Sytem.out.printIn () ; //initialize random number generator public static void initializeRandom () { r = new Random () ; } // swap arr [i] and arr [j] in arra private void swap 9 int [] arr, int i, int j) int temp = arr [i] arr [i] = arr [j] //shuffle Deck public void shiffle () //generate a random premutation by picking a random //card from those remaining and putting it in the int index ; for ( int i = NUMECARDS1 ; i>0; i) index = r. nexInt 9i+1 ) ; //int from 0 to i swap (mydeck, i, index ) ; Here is a simple program that uses the Deck class: public class Decmain public static main ( String args [] ) Deck d = new Deck (); Deck.intalizeRandom () ; d. shuffle () ; d. writeDeck() ; 

Note 


Array of class Objects 
Supppose a large card
tournament needs to keep track of many decks. the code to do this could
be implemnt with an array of Deck: public class ManyDecks private Deck [] allDecks private final int NUMCARDS = 500; // contructor public ManyDecks () allDEcks = new DEck [NUMCARDS]; for 9 int i = 0; i < NUMDECKS; i ++ ) allDEcks [i] = new Deck (); // shuffle all the decks public void shuffleAll () //seed the random number generator for shuffling Deck.intalizeRandom (); //shaffle for ( int i =0; i< NUMDECKS; i++ ) allDEcks [i]. shuffle (); //write contents of all the decks public void printDecks () for ( int i= 0; i <NUMDECKS; i ++ ) allDecks [i]. writeDeck () 

Note 
The statement allDecks = Deck [NUMDECKS] ; creates an array, allDecks, of 500 Deck objects. The default initialization for these Deck object is null. In order to initialize them with actual decks, the Deck constructor must be called for each array element. This is achieved with the for loop of the ManyDecks constructor. 

Analyzing Array Algorithms 
Example 1 (a) Deiscuss the efficiency of the countNegs method below. What are the best and worst case configurations of the data? (b) What is the big O run time? (c) What is the loop invariant of the for loop? //Precondition: arr[0],....,arr [arr.length1] contain integers //Postcondition: number of negative values in arr has been returned public static int counNegs (int [] arr ) int count = 0; for ( int i=0; <arr.length; i ++ if (arr [i] <0) count++; return count; Solution: (a) This algorithm sequentially examines each element in the array. In the best case, there are no negative elements, and count++ is never executed. In the worst case, all the elements are begative, and count++ is executed in each pass of the for loop. (b) The run time is O (n), since each element in the list is examined. (c) The loop invariant for the for loops is count + number of negative values in arr[0],...,arr[i1], and 0< i < arr. length Loop invariants for array algorithms can be nicely illustrated with a diagram showing a snapshot of what is happening. Each rectangle represents a portion of array arr. The labels on the top of the rectanguilar are array indexes for elements at the begining and end of each portion. arr.length  1 0 i  1 i


Example 2 The code fragment below inserts a value, num, into its correct position in a sorted array of integers. (a) Discuss the efficiency of the algorithm. (b) What is the big O run time of the algorith? (c) What is the loop invariant of the while loop? //Precondition: arr[0],....,arr[n1] contain integers sorted in // increasing order. n < arr.length // Postcondition: num has been inserted in its correct position //find insertion point int i = 0; while (i < n&& num > arr [i]) i++ //if necessary, move elements arr [i]...arr[ni] up 1 alot for 9int j=n; j>= i+1; j) // insert num in ith slot and uodate n arr [i] = num; n++ Solution: (a) Inthe best case, num is greater thn all the elemnts in the array. Because it gets inserted at the end of the list, no elements must be moved to create a slot for it. The worst case, num must be inserted in the first slot, arr[0], and every element in the array must be moved up oneposition to create a slot. 

Note 
This algorithm
illustrates a disadvantage of arrays: insertion and deletion of an
element in a order list is since, in th worst case, it may involve
moving all the elemts in the list (b) Insertion or deletion of a single element in a order list is O (n). Note that idf n elements must be inserted (or deleted) with this algorithm, the algorithm becomes O (n) (c) The loop invarian for the while loop is num > arr [0], num > arr [1],...,num > arr[i1], where 0 < i< n Here is the diagram that illustrates this loop invariant:] 0 i  1 i n  1


Arrays List 
This section contains the
material that Level A students need to know. Lvel AB students should
also see Chapter 11 for a full discussion of arraylist and the other
container classes. 

The ArrayList Class 
The ArrayList class is part of
the java.until, one of Java's standars packages. An ArrayList provides
an alternative way of storing a list of iobjects and has the followinh
advantages over an array:
Then why use an array?
Well, an array has these advantages over an ArrayList:


The Methods of ArrayList 
You should know the
following methods: ArraysList ( ) Constructs an empty list. int size ( ) Returns the number of elements in the best list. bloolean add (Object obj.) Appends obj to the end of the list.Always returns true. Object get (int index, Object element) Returns the element at the specificied index in the list. Object srt ( int index, Object element) Replaces itemat specified index in the list with specified elemet.Returns the eleement that was previously at index. void add (int index, Object element) Inserts element at specifiied index in list.If the insertion is not at the end of the list; shifts the elemet currently at that position and all eleemnts following it one unit to the right (i.e.,adds 1 to their indexes). Adjusts size of list. Object remve (int index) Removes and returns the elemnt at the specificified index in the list. Shifts all elements following that element one unit to the left (i..e.,subtracts 1 from their indexes). Adjusts size of list. 

NOTE 
Each method above that
has an index parameter add, get, remove, and set throws an
IndexOutOfBoundsException if index is out of
range. For get, remove, and set, index is out
of range if index < 0 l l index >= size ( ) For add, however, it is OK to add an element at the end of the list. Therefore index is out of range if index < o l l index > size ( ) 

Using arrayList 
Example 1 //create an ArrayList containing 0 1 4 9 ArrayList list = new ArrayList ( ) ; for ( int i = 0; i<a; i ++) list.add(new Integer (i*i)); Integer intOb = (Integer) list. get ( 2) ; //assings 4 to intOb //leaves a unchanged Objectc x = list.set ( 3, new Integer ( 5 )) ; // list is 0 1 4 5 x = list.remove (2) ; //list is 0 1 5 //x contains 4 list.add(1, new Integer (7) ) ; //list is 0 7 15 list.add (2, new Integer (8)); //list is 0 7 8 15 

NOTE 
If the line Integer int Ob = ( Integer) list. get ( 2); is replaced with Integer intOb = list.get (2); a compiletime error will occur. This is because the types on the left and right sides are now incompartible: The left side, intOb, is an Integer, while the right side, list.get (2), is an Object. To avoid this problem, an explicit cast to Integer is required on the right side. Example 2 //traversing an ArrayList // print the elemts of list, one per line for ( int i = 0; i <list.size ( ) ; i ++ ) System.out.println (list.get ( i )) ; 

NOTE 
The object list.get
( i) do not need to be cast to their actual types before printing. The above code assumes that each object in the list has a toString method that enables it to be printed in a meaningful way. Examople 3 /* Precondition: ArrayList list contains Integer values * sorter in increasing order *Postcondition: value inserted in its correct position in list */ public void insert ( ArrayList list, Integer value) { int index = o; //find insetion point while (index < list.size() && value.compareTo(list.get(index)) > o) index++; //insert value list.add(index,value); } 

NOTE 
Suppose value is larger than all
the elements in list. Then the insert method will throw an
IndexOutOfBoundsException if the first part of the test is omitted,
namely index<list.size(). 

TwoDimensional Arrays 

Level AB Only 
A twodimensional array
(matrix) is often the data structure of choice for objects like board
games, tables of values, theater seats, and mazes. Look at the following 3 x 4 matrix: 2 6 8 7
1 5 4 0 9 3 2 8 

Level AB (continued) 
If mat is the matrix variable,
the row subcripts go from 0b to 2 and the column subcripts go from 0 to
3. The elemet mat [1] [2] is 4, whereas mat [0] [2] nad mat [2]
[3] are both 8. As with one dimensional arrays, if the subcripts are
out of range an ArrayIndex outOfBoundsException is thrown. 

Declarations 
Each of the following declares a
twodimensional array: int [] [] table; //table can reference a 2d array of integers //table is currently a null reference doubled [] [] mat = new double [3] [4]; //mat references a 3 x 4 //array of real numbers. // Each element has value 0.0 String [] [] strs = new String [2] [5]; //strs references a 2 x 5 //array of String objects. //Each element is null An initializer list can be used to specify a twodimensional array: int [] [] mat = { {3,4,5}. //row 0 {6,7,8} }; //row 1 This defines a 2 x 3 rectangular array (i.e.., one in which each row has the same number of elements). The initializer list is a list of lists in which each inside list represents a row of the matrix. The quantity mat.length represents the number of rows. For any given row k, the quantity mat [k].length represents the number of elements in that row, namely the number of colums. (Java allows a variable number of elements in each row. Since these "jagged array" are not part of the AP Java sebset, you can assume that mat [k].length is the same for all rows k of the matrix, i.e., that the matrix is rectangular.) 

Processing a
TwoDimensional Array 
Example 1 Find the sum of all elemnets in matrix mat: //Precondition : mat is initialized with integer vakues int sum = 0; for (int r=0; r<mat[r].length; c++) sum + = mat [r] [c]; 

NOTE 
1. mat [r] [c] represents
the rth row and the cth column. 2. Rows are numbered ffrom 0 to mat.length1 and columns are numbered from 0 to mat [r].length1. Any index that is outside these bounds will generate an ArrayIndexOutOfBoundsException. Example 2 Add 10 to each element in row 2 of matrix mat. for (int c=0; c=<mat[2].length; c++) mat [2] [c] += 10; 

Leval AB NOTE (continue) 
In the for loop you can
use c<mat [k].length, where 0< k< mat.length, since each row
has the same number of elemnts. Example 3 The major and minor diagonals of squre matrix are defined as follows: You can process the diagonals as folows: int[] [] mat = new int [SIZE] [SIZE] ; //SIZE is a constant int value for 9int i=0; i<SIZE; i ++) Process mat [i] [i]; //major diagonal OR Process mat [i] [SIZEi1}; //minor diagonal 

TwoDimensional Array as
Parameter 
Example 1 Here is a mathod that counts the number of negative values in a matrix. //Precondition: mat initialized with integers //Postcondition: returns count of negative values in mat public static int countNegs (int [] [] mat) { int count = 0; for (int r=0; r<mat.length; r++) if (mat[r] [c] <o) count++; return count; } A method in the same class can invoke this method with a statement such as int negs = countNegs (mat); Example 2 As with onedimensional arrays there are two approaches for reading elements into a matrix. Approach 1 

Level AB (continued) 
//Precondition : rows X
cols matrix mat declared //Postcondition: elemts of mat read from keyboard public static void getMatrix (int [] [] mat, int rows, int cols) { for (int r=0; r<rows; r++) { System.outprintln("Enter row:"); for (inr c+0; c<clos; c++) mat[r] [c] = IO.readInt (); //read user input } } To call this method: //prompt for number of rows and columns int rows = IO.reaInt () ; //read user unput int cols = IO.readInt () ; // read user input int [] [] mat = ner int[rows][cols]; getMatrix(mat, rows, cols); Approach 2 Let the return type of the method be a twodimensional array. //Precondition: matrix undefined. Number of rows and columns know //Postcondition: returns matrix containing rows x cols integers // read from the keyboard public static int [] [] getMatrix(int [] [] getMatrix (int rows, int cols) { int [] [] mat = new int [rows] [cols]; for (int r=0; r<++) { System.out.println("Enter row:"); for (int c=0; c<cols; c++) mat [r] [c] = IO.readInt(); //read user input } return mat; } To call this mathod: //prompt for number of rows and columns int rows = IO.readINt (); //reas user input int cols = IO.readInt(); //read user input int [] [] mat = getMatrix(rows, cols); 