lect12a
arrays

Arrays vs Lists

We have seen lists, with their methods get(int) and add(Object), as a way of large sequences of data.

By the way, lists (which can hold any item, at each index) are very much like Strings (which hold a char at each index).

We now show yet another way of collecting sequences of data: arrays.

action	`String`	`List`s	arrays
The type	`String`	`java.util.LinkedList<Double>`	`double[]`
constructor	`new String(stringLiteral)` (or, just `stringLiteral`)	`new java.util.LinkedList<Double>()`	`new double[50];`
add-at-end	—	`myList.add( 23.4 );`	—
access ith element	`myStr.charAt(i)`	`myList.get(i)`	`myArray[i]`
change ith element	— (`String`s are immutable)	`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	`myStr.length()`	`myList.size()`	`myArray.length`
convert to `String`	`myStr`	`myList.toString()`	`java.util.Arrays.toString(myArray)`
Can hold primitive types?	no (only `char`s)	no	yes

Exercise

Hmns r gd t ndrstndng sntncs, vn wth ll vwls rmvd.

We'll write three versions of removeVowels, which is given a String/list-of-Character/array-of-char, and it returns a another String/list-of-Char consisting of all the non-vowels in the input. For example, removeVowels( "Humans are good at understanding sentences, even with all vowels removed." ) would return the above answer as a String.

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; 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.
When making a variable which holds an array, you must not only initialize the array (“allocate” it), but you must furthermore initialize the contents of the array:
int[] data; data = new int[500]; // Initialize (allocate) the array itself. for (int i=0; i<data.length; ++i) { data[i] = i*i*i; // Initialize the value stored at index i. }
(This extra step corresponds to adding values to a list; however, it's okay to initialize a list-variable without immediately filling it with data. With arrays, you will get NullPointerExceptions if you don't initialize it.)
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”.²

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)

As mentioned, an array can only get and set, while a java List can do all that and more. You'll see in 220 that arrays can be used to implement class List. What follows are examples where many people would content themselves with 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).

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; }
  
  }

¹ 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. ↩

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!

↩

home—info—labs—hws—exams
textbook—java.lang docs—java.util docs—archive

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

lect12aarrays

Arrays vs Lists

Exercise

Arrays vs Lists

Examples of when to use arrays (rather than lists)

Case Study

lect12a
arrays