CS112 Lecture: Arrays and CollectionsLast revised 3/18/09Objectives:1. To introduce the use of arrays in Java2. To examine some typical operations on arrays and introduce the appropriate patterns3. To introduce sorted arrays4. To introduce multi-dimensional arrays5. To introduce collections Materials: 1. Projectable and demonstrable version of non-array and array versions of "reverse list of numbers" program, plus improved version allowing arbitrary size.2. Projectable version of excerpt from “array of runners” version of steeple chase robot problem3. Projectable version of code excerpts illustrating array operations: Figure 14.5 in book, sum, maximum, searching, sorting, expansion4. ArrayParametersDemo.java, .class + handout5. Projectable version of ordered array of runners example from text - Figures 14.26, 14.27, 14.28 plus code for RaceStatistics class6. Excerpts from AddressBook class given to students for project 37. Non recursive solution to word frequency problem from recursion lecture8. Projectable version of YearlyCalendar example from textI. Introduction to ArraysA. Consider the following problem: we want to read in a list of 5 numbers and print them out in reverse order.1. Clearly, we need to read all of the numbers before we can print any of them out. This means we have to store all the numbers in variables.2. One solution would be to use 5 variables:PROJECT BadReverse.javaDEMO3. However, needing to have 5 distinct variables is cumbersome, and an approach like this would become essentially impossible if we were working, say, with 100 numbers, or 1000, or 10,000 !14. To deal with situations like this, Java - like most programming languages - provides a built in data structure called an array. In Java, a variable is declared to be an array by following the type name with a pair of square brackets ([]), and individual elements in the array can be referenced by following the name of the variable with a subscript enclosed in square brackets. In particular, our example could be handled as follows:PROJECT GoodReverse.javaDEMONote that the complete program is now shorter than the original program - and would be much shorter if we compared programs for a larger number of values. Further, it could easily be modified to work with any number of numbers by changing the initial declaration of the size of the array. Every Java array has a field called length with specifies the number of elements specified when the array was created. (Note that, for arrays, this is a field, not a method, so no () are used.)5. In fact, it would be easy to create a variant of this program which allows the user to specify the number of numbers when the program is run.PROJECT EvenBetterReverse.javaDEMOB. Recall that earlier we say that Java has two basic kinds of data types: primitive types and reference types. The latter category has two subcategories - objects and arrays. Arrays in Java can be thought of as a special kind of object); however, the formal definition of the language distinguishes them because of slight differences in the way they are used. (For example, arrays have no methods).C. To use an array in Java, you must:1. Declare an array variable - two alternative, but equivalent syntaxes:< type > [] < variable name > (preferred)Example: int [] number;or< type > < variable name > [] (“C” style declaration)Example: int number [];22. Allocate storage for the array, using new< variable name > = new < type > [ < size > ](Note: the type used here must be the same as the type used when declaring the variable; and the size must be known at the time the array is created - it can either be an integer constant, or an integer variable or expression; in the latter case, the value of any variables at the time the array is created are what is used.)Example: number = new int [5];This can be combined with declaration< type > < variable name > [] = new < type > [ < size > ]Example: int [] number = new int [5];3. You can nowa) Refer to the array as a whole by using its nameb) Refer to the individual elements of the array by using< variable name > [ < subscript > ]where < subscript > is an integer in the range 0 .. size - 1Examples:number[3]number[2*i+1](Note: Java uses zero-origin indexing. An array declared with size n has elements 0 .. n - 1). So, the first element is called [0], the second [1] ...Note the distinction between the variable name all by itself - which stands for the entire array, and the variable name plus subscript, which stands for an individual element of the array. Operations such as arithmetic, input, and output are done on the individual elements.Example: If a given building is a single family home, you can address mail directly to it. If it is an apartment building, you must specify a particular apartment by giving an apartment number as well. You can 3refer to the whole building for certain purposes - such as tax assessment!- but most of the time you will need to refer to a specific apartment by number.c) Refer to the number of elements in the array by< variable name > . lengthExample: number.lengthD. One important characteristic of an array is that all of the elements of the array have the same type. The type of the elements of an array, however, can be any valid Java type.1. A primitive type (boolean, char, int, etc.) - as in the example above2. An object type. In this case, it is necessary not only to create the array, but also to create the individual elements of the array - since they are objects.EXAMPLE: Consider the robot relay race problem, again. We could extend the program to handle any number of robots, as follows.PROJECT Code excerpt int [ ] startAves = { 1, 5, 7, 13 };SteepleChaseRobot [ ] runner = new SteepleChaseRobot[startAves.length];for (int i=0; i < startAves.length; i ++){ if (i < startAves.length - 1) runner[i] = new RelaySteepleChaseRobot( 1, startAves[i], Directions.EAST, 0); else runner[i] = new SteepleChaseRobot( 1, startAves[i], Directions.EAST, 0);}for (int i = 0; i < startAves.length; i ++) robot[i].runRace();3. Another array type - yielding an array of arrays, or a multidimensional array. (We’ll talk more about this later.)E. Of course, it is possible to have an array of type char. How does this differ from a String?41. In some programming languages (e.g. C) there is no distinction - strings in C are just arrays of characters.2. In Java, type type String is a class