ibarland,
jdymacek

home—info—exams—lectures—labs—hws
Recipe—Laws—lies—syntax—java.lang docs—java.util docs

lect14b
arrays

Reading: Chapter 7.
Some powerpoint slides for Chapter 7 are also available on the course's Blackboard (WebCT) page.

Arrays vs Lists

Suppose we want to process the temperature every day in January. How can we represent that data?
double[31], which we use as:

 
java.util.Random randy = new java.util.Random();
double LO = 20.0;
double HI = 40.0;

double[] temps;                               // Declare.

temps = new double[31];                      // Allocate.


temps[0] = 35.0;      // We'll fill the array with random numbers.
temps[1] = 22.7;
temps[2] = 30.0;
temps[3] = //...
//...
temps[30] = 23.4;


// Isn't there a better way to initialize each location?
// Yes -- use a loop, to get the *computer* to count 0..30 for us:

// Initialize our model with random numbers between LO and HI.
for (int i = 0; i<temps.length; ++i) {
  temps[i] = LO + (HI-LO)*randy.nextDouble();  // Initialize.
  }

In BlueJ, we'll inspect the array. It's an object which has fields named “0”, “1”, … through “30”. (You might notice it also has a field named “length”.)

Examples of when to use arrays (rather than lists)

Or suppose that we want a music-program to store information about each measure of a symphony. (Note that music scores are indexed by measure#; during rehearsal it's common to say “let's start from measure 95”.)

52 cards in deck:

public static final int NUM_SUITS = 4;
public static final int NUM_RANKS = 13;

Card[] deck;

cards = new Card[NUM_SUITS*NUM_RANKS];    // No 'Card' objects created, yet!

for ( int i = 0;  i<temps.length; ++i) {
  deck[i] = new Card( (i%NUM_RANKS)+1, i/NUM_RANKS );
  }

Note that a pack of cards (where you deal cards from, and the pack shrinks) is actually more appropriate to use a list.

Representing the Monopoly board: exactly 40 locations. (Presumably, you'd have a class Location to represent one location.¹

Note that using % with the array size is common:

Location[40] board;
board = new Location[40];
 // ... spend time initializing the array contents ...
PairODice pd = new PairODice();


int position = 33;
pd.roll();
position = (position + pd.getTotal()) % board.length;

The ordinal suffix for numbers 0...99. That is, "0th", "1st", "2nd", "3rd", etc..
String[] suffixes; suffixes = new String[100]; suffixes[0] = "th"; suffixes[1] = "st"; suffixes[2] = "nd"; //...
Okay, you can also think of a better way to initialize this array. What advantages does a lookup table have, over a method which returns the suffix (doing some calculation each time)? Not too much. However, if this is a result which is called tens of thousands times per second, then using a table might be a significant help. (Lookup tables are usually more important in scientific calculation.)

Note that these suffixes might be one place to use Java's helpful automatic-array initialization syntax:
String[] suffixes = { "th", "st", "nd", "rd", "th }
Note that this fixes the array's size at 5 (in this example). See more details in the book's Chapter Seven.

Case Study

Example: count how many times each character occurs in a String.

representing char: Characters are represented by short ints in Java; most ordinary letters are encoded by numbers in 32...127. Java lets you do arithmetic on char: try (in Code Pad)

'a',

'a'+0,

(char)99
Note that unlike casting for double and int, there aren't methods inside class Character to help with these conversions (?*#%!); casting is the only way to explicitly convert between char and int.

'a'+1,

'a'+'1' (not concatenation!, nor incrementing by 1),

'm'-'a' (“how many letters after 'a' is 'm'?”),

'm' > 'a',

¡Unicode characters have a larger range!: (char)8617 or (char)2000 or (char)21488.

We can use this conversion between int and char to help us have letters correspond to indices: 'A' will be at index 0, 'B' will be at index 1, etc.. In general, for a char ltr, if ltr holds an upper-case letter then we can use ltr - 'A' as an index.

/** Adapted from Java Foundations, Chpt 7, example 7.3
 */
class LetterCounts {
    public static final int NUM_LETTERS = 26;  // Named constant.

    private String msg;
    private int otherCount;
    private int[] upperCounts = new int[NUM_LETTERS];  // Declare and allocate.
    private int[] lowerCounts = new int[NUM_LETTERS];


    /** Constructor.
     * @param src A String to count the letters of.
     */
    public LetterCounts( String text ) {

        msg = text;
        otherCount = 0;

        // Initialize our declared, allocated arrays:
        for ( int i = 0;  i < NUM_LETTERS; ++i ) {
            upperCounts[i] = 0;
            lowerCounts[i] = 0;
            }

        // Now, look at every character in our argument:
        for ( int i = 0;  i < text.length();  ++i ) {
            char ltr = text.charAt(i);
            if ('A' <= ltr && ltr <= 'Z') {
                upperCounts[ ltr-'A' ] = upperCounts[ ltr-'A' ] + 1;
                }
            else if ('a' <= ltr && ltr <= 'z') {
                ++lowerCounts[ ltr-'a' ];
                }
            else {
                ++otherCount;
                }
            }

        }


  /** Return a String with the results of counting the letters.
   * @return a String with the results of counting the letters.
   */
  public String toString() {
    String resultSoFar = "";
    for (int offset=0; offset < NUM_LETTERS; ++offset ) {
      resultSoFar += (char)(offset+'A') + ": " + upperCounts[offset] + "\t"
                  +  (char)(offset+'a') + ": " + lowerCounts[offset] + "\n";
      }
    return resultSoFar + "Other: " + otherCount;
    }

  public int[] getUpperCounts() { return this.upperCounts; }
  public int[] getLowerCounts() { return this.lowerCounts; }
  
  }

Arrays vs Lists

Arrays hold a fixed number of items, whereas lists can hold any number of items.

reminder: Sometimes people confuse the variable referring to the list, with the loop-variable which refers to an element of the list. They are very different!

You don't confuse an apple with a bag-of-apples; you don't confuse a bus-passenger with a bus; so similarly don't confuse an item with a collection-of-items.

To access elements of an array by index, use […]; for lists, use the get(…) method. That is, myArray[3] vs. myList.get(3). While the array syntax is shorter, it's a bit confusing to introduce a whole new type of punctuation which is really just a method-call in disguise.
Both arrays and lists let you replace the item at a certain index: myArray[3] = newVal; (see powerpoint/book), vs. myList.set( 3, newVal );. Thus the square-bracket notation can mean either get or set, depending on context. (Again, this is a trade-off between shorter notation, and having brand-new notation which we didn't have to worry about before.)
In an array, there is no way to automatically add or remove a new element in the middle, and have all the other elements slide over to fill/create the gap. Lists have versions of remove and add which do this, taking an index as (one of) their arguments.
When calling a constructor for type int[], you must provide one argument: the size of the array (which is then forever fixed). But instead of writing new int[](100), you write new int[100].
In fact, this is the first time when the declared-type and the new don't quite match up: int[] data = new int[100];.
To get the size of a list, you use the method size(). To get the size of an array, you use the field length: That is, myList.size() vs. myArray.length. (Note the lack of parentheses, since we're accessing a field directly, not calling a getter-method).
In both arrays and lists with N elements, valid indices are in the range [0,N) (that is, N-1 is the largest valid index). Far and away the most common runtime beginner-mistake with arrays and lists is “index out of bounds exception”, from trying to use N (or occasionally -1) as an index.
Arrays can hold primitive values, whereas lists only contain actual objects. (This drawback is ameliorated by the wrapper classes and auto-boxing, as we saw.)
The built-in toString for arrays is pathetic. Instead use the static method static java.util.Arrays.toString(Type[]).
Note the ‘s’ on the end of ‘Arrays’. (The class java.util.Arrays is a utility class — i.e. full of static methods — whose purpose is to provide the methods which should have been built-in to the first version ²of Java.
Don't get confused by documentation for similarly-named classes java.lang.reflect.Array or java.sql.Array, yikes!

In practice, lists prove much more flexible than arrays: it's much more common to have data of the form “0 or more data” than “exactly 100 data”.³

action	`List`s	arrays
The type	`java.util.LinkedList<Double>`	`double[]`
constructor	`new java.util.LinkedList<Double>()`	`new double[50];`
add-at-end	`myList.add( 23.4 );`	—
access ith element	`myList.get(i)`	`myArray[i]`
change ith element	`myList.set(i,23.4)`	`myArray[i] = 23.4`
increment ith element (useful only when the collection holds numbers)	`myList.set(i, myList.get(i)+1 )`	`myArray[i] = myArray[i] + 1` or `myArray[i] += 1` or `++myArray[i]`
determine the size/length	`myList.size()`	`myArray.length`
convert to `String`	`myList.toString()`	`java.util.Arrays.toString(myArray)`
Can hold primitive types?	no	yes

main

BlueJ has a rich interface for interacting with Java programs: you can call any method of any class. Most IDEs have a much more limited interface: They let you choose a certain class, but then you can only call one specific (static) method of that class:


/**
 * Write a description of class Acronym here.
 * 
 * @author (your name) 
 * @version (a version number or a date)
 */
public class Acronym {

  /** A test driver which makes an acronym from its input,
   * printing the results to SYstem.out.
   * @param args The words of input.  Each String must be non-empty (and non-null).
   */
  public static void main( String[] args ) {
    System.out.println( "A " + args.length + "-letter acronym for "
                      + Acronym.wordsToString( args, " ", "\"", "\"" )
                      + " is "
                      + "\"" + Acronym.acronym(args) + "\""
                      + "." );
  }

  /* Return a single string, concatenating each word in an array of Strings.
   * @param words the individual Strings.
   * @param between What to put in between each word; usually " " or ", ".
   * @param before What to start the answer with; often "".
   * @param after What to finish the answer with; often "".
   */ 
  public static String wordsToString( String[] words, String between, String before, String after ) {
    String innards = "";
    if (words.length > 0) {
      innards += words[0];
      }
    for ( int i=1;  i < words.length;  ++i ) {
      innards += between + words[i];
      }
    return before + innards + after;
    }
    
  /** Return an acronym for an array-of-words, each letter capitalized.
   * and separated by a ".".
   * @param words An array of single words.  Each String must be non-empty.
   * @return an acronym for an array-of-words, each letter capitalized.
   */
  public static String acronym( String[] words ) {
    String asf = "";   // "acronym so far"
    for ( int i=0;  i < words.length;  ++i ) {
      asf += words[i].toUpperCase().charAt(0) + ".";
      }
    return asf;
    }
      
      
  }

There is nothing special about the method-name “main” except that it's been chosen as the de facto starting method by most IDEs. The input argument -- an array of Strings -- is a convention from the UNIX operating system. This input is the primary way your java program gets initial information from the operating system, when your java program is launched: a fixed number of words. For example, from a UNIX shell:

java Acronym hello, world

Review and different perspective

Arrays are like lists, but:

Fixed size -- when the array is created with "new", its size is set in stone
instead of "new LinkedList<String>()", a new syntax: "new String[50]"
Instead of "l.get(7)", a new syntax: a[7]
instead of "l.add("meow", 8)", a new syntax for the same thing: a[8] = "meow"
instead of "l.add(..)", … nothing! (You can't add new things to the end.)
Instead of "l.size()", a new syntax: a.length

Why a new data structure, if a List can already do everything an array can, and yet the array is limited to a fixed size?

Shallow answer: They gave it a special syntax which saves some typing once you've learned it.
Good answer: When we want to add/remove from the collection as time passes, use a list.
Best answer: sometimes the physical world corresponds to fixed-size collections, and the 0th law of programming tells us that our data should reflect what we're trying to model.
class Motel { String name; String address; int numRooms = 57; Room[] rooms = new Room[this.numRooms]; //... }
Subtle observation: For some data, the exact index of the data is also part of the information. For instance, consider the high temperature for each day in January. double[] is an appropriate type:
double[] temps = new double[31]; /* Here, have code which initializes all 31 elements of the array */ temps[5] // Knowing that the high occured on Jan.06 is part of the data.

If a list is a line-up bag of suspects (er, objects), then an array is a bus of objects.

When creating an array, initialize all the fields immediately. If you can't, that's a good indication that you want to use a List instead.

(Note that when you add into the middle of a list, it changes what index each later object has. With an array, you can't add into the middle, so that isn't an issue. You can only overwrite the existing contents of a particular bus-seat-#.)

Processing arrays: for-loops are very natural. Also, for-each loops still work, and are perfect when you don't need the index-number to process the element.

double[] data;
data = new double[500];
java.util.Random r = new java.util.Random();

// Initialize array contents with random numbers in [0,1).
for (int i = 0;  i < double.length;  ++i ) {
  data[i] = r.nextDouble();
  }


// Find the average:
double sumSoFar = 0.0;

for ( double d : data ) {
  sumSoFar += d;
  }

double average = sumSoFar / data.length; 
// N.B. if data.length is 0, then floating-division gives Double.NaN.

Hmm... Some locations are properties (with rents, sale-prices, etc.); other locations are events (community-chest, Go, etc.). How to have one single class that can represent both these elements which have many differences, but also many similarities (they all have images, might have people on them, can trigger events, etc.).

Really this is two problems: union types (properties vs. events-only), and shared functionality (what both types do). Interfaces and inheritance (next week) provide a good solution to these problems!

↩

² Usually, in Java, you can extend classes to give them additional behavior. However, in Java, you can't extend array classes, so this class was kludged on. ↩

³ And when using a list, there are two common choices: LinkedList<Type> and ArrayList<Type>. Nearly always, ArrayList<Type> is the better choice. Despite its name, ArrayList is not an array; it's a list. ↩

home—info—exams—lectures—labs—hws
Recipe—Laws—lies—syntax—java.lang docs—java.util docs

©2007, Ian Barland, Radford University
Last modified 2007.Dec.06 (Thu) Please mail any suggestions
(incl. typos, broken links)
to iba�rlandrad�ford.edu

lect14barrays

Arrays vs Lists

Examples of when to use arrays (rather than lists)

Case Study

Arrays vs Lists

main

Review and different perspective

lect14b
arrays