Arrays and Array Lists

Shuould array indices star at 0 or 1?

One-Dimensional Arrays



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 (N-1). If a negative subcript is used, or a subcript k where k-N, 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.

Example

All 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 List


Small 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

  1. The array subcripts go from 0 to names. length- 1; therefore, the test on i in the for loop must be strictly less than nemes. length.
  2. Length is not a method and therefore is not followed by parentheses. Contrast this with String objects, where length is a method and must be followed by parentheses. For example,
        
         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

  1. There are no square brackets for the argument of the call.
  2. An alternative heatder for the meyhod is
               public static int findMin ( int arr [])

  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.

               
Before the method call:
At the start of the method call:

Just before exiting method:
After exitong the method:


      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 = NUMECARDS-1 ; 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
  1. There is no evidence of  the arry that holds tghe deck of cards myDeck is a private instance variable and is therefore invisible to clients of the DEck class.
  2. The random number generator should be initialized just once in a program that shuffles decks od cards. This is why it is declared as a static variable. ( note static variables will not be tested on the AP exam.)
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.length-1] 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[i-1], 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
count = number of negatives in here
still to be examined

                                         

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[n-1] 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[n-i] up 1 alot for 9int j=n; j>= i+1;  j--)
          // insert num in i-th 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[i-1], where 0 < i< n

   Here is the diagram that illustrates this loop invariant:]

0                                                        i - 1   i                                    n - 1
num > all elements in here
still to be examined

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:

  • The length of an ArrayList shrinks and grows as needed in a program, whereas an array has a fixed length that is set when the array is created.
  • in a ArrayList L, the last  slot is always L. size ( ) -1, wheeas in a partially filled array, you, the programmer, must keep track of the slot currently in use.
  • For an arrayList, you can do insertion or deletion with just a single statement. Any shifting of elements is handled automatically. In an array, hpwever, insertion or deletion requires you to write the code that shifts the elements.

  Then why use an array? Well, an array has these advantages over an ArrayList:
  • It is easy to store numbers (primitive types like int or double) in an array. Since an ArrayList must be placed in wrapper classes ( like Integer or Double) before they can be inseted in an ArrayList.
  • It is easy to retrieve numbers from an array. If inList is an array of int, intList [k] automatically has type int. an element retrived from an ArrayList is of type Objects and must be cast to its actual type. If the elements are numbers (integer or Double), the methods intValue ( ) or doublValue (0 must than be invaked before the numerical values can be used.
  • It is more efficient to use an array for a list of numbers because there is no wrapping, or casting of the elements involved.
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 compile-time 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().

Two-Dimensional Arrays
 Level AB Only
  A two-dimensional 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 two-dimensional array:

int [] [] table;   //table can reference a 2-d 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 two-dimensional 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 Two-Dimensional 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.length-1 and columns are numbered from 0 to mat [r].length-1. 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] [SIZE-i-1};       //minor diagonal
Two-Dimensional 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 one-dimensional 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 two-dimensional 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);