AP Computer Science A Prep, 2024 - Rob Franek 2023

9 ArrayList
Part V: Content Review for the AP Computer Science A Exam

LISTS & ArrayLists

There are two big limitations of the powerful array structure in Java: an array has a fixed length, and it can store only one type of data. If you wanted to represent, say, a friend’s collection of action figures, an array would require all of the action figures to be the same type. Generally speaking, they must all be flying superheroes, or they must all have protective body armor, etc.

Likewise, a collection of action figures represented as an array could store only a fixed number of action figures, no more and no less. If there are extra, unused slots, they stay there, which could be problematic if you have an array of helmeted heroes, and you try to remove the helmet from every element in every index of the array. Once you reach the first empty spot, there is no hero and therefore no helmet, so the directions do not make sense; in Java, the compiler will return a NullPointerException for this situation.

There are advantages and disadvantages to every structure that we study in Java.

An ArrayList addresses both of these issues. An ArrayList object is dynamically sized, expanding and compressing as elements are added and removed. An ArrayList can also store multiple types of data, without limit.

Let’s use an example to understand the advantages and disadvantages of arrays versus ArrayLists. Consider your lunch bag that you take to school. If you wanted to represent your lunch bag using an array or ArrayList structure, which would be more accurate?

Naturally, the answer to this question depends on (1) the details of the objects in the bag—in this case, the types of lunch items—and (2) the programmer’s choice of which is more appropriate. If your lunch contains a sandwich object, a fruit object, and a drink object, the ArrayList structure might be a better choice. Furthermore, as the components of the lunch are removed, the lunch bag theoretically shrinks (or can shrink). An ArrayList seems appropriate.

Let’s consider the same lunch example, but this time, suppose the items are stored in a plastic container with compartments. Regardless of whether you have not yet eaten your lunch, you are done with your lunch, or it’s currently anytime in between, the number and setup of the compartments do not change. We will discuss a workaround for “tricking” the array into thinking the lunch objects are all the same type. These facts and abilities render an array structure more appropriate than an ArrayList.

To further demonstrate the usefulness of an ArrayList structure, note that it is also possible to create a typed ArrayList, which allows only objects of the same type to be stored in the list. This structure combines useful aspects of both arrays and ArrayLists.

In order to instantiate an ArrayList called lunchBag that will store the various components of our lunch, we use the following line of code:

ArrayList lunchBag = new ArrayList();

Note that, unlike the syntax we use for instantiating an array, neither the type of object nor the length of the list is defined initially.

In order to access data from within the list, particular methods must be invoked; unlike for array structures in Java, there is not a convenient bracket notation available with lists. To return the second object, an Apple object, in the ArrayList and store it using the variable food, the line of code would be

Apple red = lunchBag.get(1);

There are several other useful methods available in the List class, and they are all mentioned in the AP Exam Quick Reference, although their functionality is (obviously) not given. These methods include add, set, remove, and size.

Bracket notation can be used only with array objects; lists must use the appropriate methods.

If the programmer decides it is more appropriate to keep the dynamic sizing ability of the ArrayList while fixing the type of data it can hold (as in an array), it would be instantiated as follows:

ArrayList lunchBag = new ArrayList();

One of the drawbacks of using ArrayList is that only objects can be stored in an ArrayList. The primitive data types int and double cannot be stored in ArrayLists. If programmers want to store integer and double data types, they must use the Integer or Double wrapper classes. Integer and Double objects can be created using integers and doubles, respectively, as parameters. For example,

Integer n = new Integer(5);

Double x = new Double(6.1);

To call the values, use the intValue() and doubleValue() methods. The following commands

int a = n.intValue();

double y = x.doubleValue();

assign a = 5 and y = 6.1.

Additionally, the AP Computer Science Java Subset includes the static variables MIN _ VALUE and MAX _ VALUE of the Integer class. These store the minimum and maximum possible values of the integer data type.

KEY TERMS

ArrayList object

dynamically sized

typed ArrayList

CHAPTER 9 REVIEW DRILL

Answers to review questions can be found in Chapter 13.

1.Consider the following code segment:

ArrayList list = new ArrayList( );

list.add(“A”);

list.add(“B”);

list.add(0, “C”);

list.add(“D”);

list.set(2, “E”);

list.remove(1);

System.out.println(list);

What is printed as a result of executing the code segment?

(A) [A, B, C, D, E]

(B) [A, B, D, E]

(C) [C, E, D]

(D) [A, D, E]

(E) [A, C, D, E]

2.Consider the following data fields and method:

private ArrayList letters;

// precondition: letters.size( ) > 0

// letters contains String objects

public void letterRemover( )

{

int i = 0;

while (i < letters.size( ))

{

if (letters.get(i).equals(“A”))

letters.remove(i);

i++;

}

}

Assume that ArrayList letters originally contains the following String values:

[A, B, A, A, C, D, B]

What will letters contain as a result of executing letterRemover( )?

(A) [A, B, A, A, C, D, B]

(B) [B, C, D, B]

(C) [B, A, C, D, B]

(D) [A, B, A, C, D, B]

(E) [A, A, B, C, D, B, D]

3.Consider the following method:

private ArrayList myList;

// precondition: myList.size( ) > 0

// myList contains String objects

public void myMethod( )

{

for (int i = 0; i < myList.size( ) — 1; i++)

{

myList.remove(i);

System.out.print(myList.get(i) + “ ”);

}

}

Assume that myList originally contains the following String values:

[A, B, C, D, E]

What will be printed when the method above executes?

(A) A B C D E

(B) A C E

(C) B D E

(D) B D

(E) Nothing will be printed due to an IndexOutOfBoundsException.

4.Consider the following code segment:

ArrayList list = new ArrayList( );

for (int i = 1; i <= 8; i++)

{

list.add(new Integer(i));

}

for (int j = 1; j < list.size( ); j++)

{

list.set(j / 2, list.get(j));

}

System.out.println(list);

What is printed as a result of executing the code segment?

(A) [2, 4, 6, 8, 5, 6, 7, 8]

(B) [1, 2, 3, 4, 5, 6, 7, 8]

(C) [1, 2, 3, 4]

(D) [1, 2, 3, 4, 1, 2, 3, 4]

(E) [2, 2, 4, 4, 6, 6, 8, 8]

Summary

o ArrayLists are lists of objects of variable length.

o An enhanced-for loop automatically performs the loop for each element of an array or ArrayList.

o A sequential search looks for an element of an array or ArrayList beginning at index 0 until the desired element is found and returns the index. If the element is not found, it returns —1.

o A binary search begins searching in the middle of an array or ArrayList and moves to higher or lower indices to find the desired element. A binary search is more efficient but can be used only on an ordered list.

o A selection sort orders an array or ArrayList by swapping lower elements to lower indices.

o An insertion sort orders an array or ArrayList by finding the appropriate location for an element, shifting other elements to take its place, and then placing the element into the appropriate location.