AP CSA Unit 7 Study Guide -- ArrayList
ArrayList Basics
● An ArrayList object contains object references.
1. Analyze the code below and Identify whether the following variables/statements
contain/return a primitive, reference, or null value.
ArrayList<Double> dList = new ArrayList<>();
ArrayList<String> sList = new ArrayList<>();
ArrayList<Integer> iList;
double[] dArr = new double[5];
String[] sArr = new String[5];
[Link]([Link]);
[Link](2.0);
[Link]("Lasagna");
[Link]("Pizza");
double x = [Link](1);
dArr[0] = [Link](0);
sArr[0] = [Link](0);
variable/statement Primitive,
Reference, or Null?
dList Reference
iList Null
dArr primitive
x primitive
dArr[0] primitive
[Link](0) reference
dArr[1] null]
sList reference
sArr primitive
sArr[0] reference
[Link](0)
reference
sArr[1] reference
AP CSA Unit 7 Study Guide -- ArrayList
2. The ArrayList dList in the previous example stores reference values of type Double.
Why does the following line of code NOT cause a compiler error when we assign it to
a primitive variable?
double x = [Link](0);
a. The variable x is unboxed into a corresponding reference variable of type
Double.
b. The wrapper class reference stored at dList index 0 is unboxed into its
corresponding primitive value.
c. The wrapper class reference stored at dList index 0 is auto-boxed into its
corresponding primitive value.
d. The variable x is autoboxed into a corresponding reference of type Double.
● The ArrayList constructor ArrayList() constructs an empty list.
3. What will the following program print?
ArrayList stuff = new ArrayList();
[Link]([Link]());
a. null
b. It will generate a Null Pointer Exception
c. A reference value
d. 0
● ArrayList is a Generic Class. Generic Classes include a type parameter inside of angle
brackets <>. In the case of ArrayList, it will specify the type of objects stored in the
list. Conventionally, a capital E for “element” is used to represent this parameter.
● When ArrayList<E> is specified, the types of the reference parameters and return
type when using the methods are type E.
● When using ArrayList<E>, it is okay to leave the angle brackets empty in the
constructor call (right side). This is sometimes called the diamond operator <>.
● ArrayList<E> is preferred over ArrayList because it allows the compiler to find errors
that would otherwise be found at runtime.
AP CSA Unit 7 Study Guide -- ArrayList
ArrayList vs ArrayList<E>:
When using ArrayList without a type parameter <E>, the list can contain a mixture of
any type of object and there is no way for the compiler to catch misuse of an object
until the program is actually run. We say it is not type safe. This may result in
ClassCastExceptions at runtime. When using a type parameter <E>, the compiler will
catch the problem, which is always preferable.
4. In the following program mark a ✓if it will not cause any issues, a C if it will crash at
compile time, and an R if it will crash at runtime to the
✔ ArrayList listA = new ArrayList();
✔ ArrayList<String> listB = new ArrayList<String>();
✔ ArrayList<Integer> listC = new ArrayList<>();
[Link]("Pizza");
[Link](2);
[Link]("Pizza");
[Link](2);
[Link](3);
int a = ((String)[Link](0)).indexOf("P");
int b = ((String)[Link](1)).indexOf("P");
int d = [Link](0).indexOf("P");
ArrayList Methods
● int size() - Returns the number of elements in the list
● add(E obj) - Appends obj to end of list and increments the size.
● add(int index, E obj) - Inserts obj at position index (0 <= index <= size), moving
elements at position index and higher to the right (adds 1 to their indices) and adds
1 to size.
● E get(int index) - Returns the element at position index in the list.
● E set(int index, E obj) — Replaces the element at position index with obj; returns the
element formerly at position index.
● E remove(int index) — Removes element from position index, moving elements at
position index + 1 and higher to the left (subtracts 1 from their indices) and
subtracts 1 from size; returns the element formerly at position index.
AP CSA Unit 7 Study Guide -- ArrayList
5. Assume names is an ArrayList<String> as shown below. What will the order of
names be after the following code runs.
Cynth Durga Anmol Sravan Arkin Rhea Annie David
String name1 = [Link]([Link]()/2);
String name2 = [Link]([Link]()/4, name1);
[Link](2);
[Link](5, name2);
[Link](“Nikolai”);
Cynth Durga Sravan Rhea Anmol Annie David Nikolai
Traversing An ArrayList
● Iteration statements can be used to access all the elements in an ArrayList. This is
called traversing the ArrayList.
● Since the indices for an ArrayList start at 0 and end at the number of elements − 1,
accessing an index value outside of this range will result in an
ArrayIndexOutOfBoundsException being thrown.
6. Which of the following loops will NOT properly traverse all elements of an
ArrayList<Integer> named nums?
a. for(int i = 0; i < [Link](); i++)
b. for(Integer num: nums)
c. for(int i = [Link](); i >= 0; i--)
d. for(int i = [Link]() - 1; i > -1; i-=1)
● Deleting and adding elements during a traversal of an ArrayList requires using
special techniques to avoid skipping or repeating elements.
7. Which line of code must be added at the commented line to make the following
remove duplicates method work correctly?
public static void removeDuplicates(ArrayList<Integer> nums){
[Link](nums);
for(int i = 1; i < [Link](); i++){
if([Link](i) == [Link](i-1)){
[Link](i);
/* insert here */
}
}}
AP CSA Unit 7 Study Guide -- ArrayList
8. Suppose no code is added after the removal in problem #7. Determine how the
given input array will be ordered after removeDuplicates(nums) executes.
input output
[13, 24, -2, 100, -2]
[2, -2, -4, 2, -4, -4]
[0, 1, 2, 1, 1, 1]
● Changing the size of an ArrayList while traversing it using an enhanced for (for each)
loop can result in a ConcurrentModificationException being thrown.
9. Match the following programs with the type of Runtime Error that will occur when it
executes. If more than one issue exists, select the error that would occur first.
Options:
NPE - Null Pointer
IOB = index Out of Bounds
CM = Concurrent Modification
CC = Class Cast
ArrayList list = new ArrayList(); ArrayList<Color> list = new ArrayList<>();
[Link]([Link]); [Link]([Link]);
[Link]([Link]); [Link]([Link]);
[Link]([Link]); [Link]([Link]);
for(int i = 0; i <= [Link](); i++){ int i = 0;
Color c = (Color) [Link](i); for(Color color: list){
Color newC = [Link](); if([Link]([Link])
[Link](i, newC); [Link](i);
} i++;
}
EXCEPTION:_______________________________ EXCEPTION:_______________________________
ArrayList<Color> list = new ArrayList<>(); ArrayList list = new ArrayList();
Color[] colors = new Color[5]; [Link]([Link]);
colors[0] = [Link]; [Link](“Spongebob”);
colors[1] = [Link]; [Link](null);
colors[2] = [Link];
for(int i = 0; i <= [Link](); i++){
for(Color color: colors){ Color c = (Color) [Link](i);
Color newC = [Link](); Color newC = [Link]();
[Link](newC); [Link](i, newC);
} }
EXCEPTION:_________________________________
EXCEPTION:_________________________________
AP CSA Unit 7 Study Guide -- ArrayList
Searching
● Sequential/linear search algorithms check each element in order until the desired
value is found or all elements in the array or ArrayList have been checked.
● Binary search will only work correctly with a sorted list.
● Binary search works by repeatedly checking the middle index of a list, comparing its
value to the target and then eliminating the half where the target cannot exits.
10.Consider the following list of ordered integers and calculate how many iterations it
would take the binary search algorithm to find it.
i 0 1 2 3 4 5 6 7
num -100 -23 0 1 10 13 18 200
Linear
Search
Binary
Search
11. Suppose we stubbornly apply the binary search algorithm to the unsorted list of
names below. Who would still be able to be found by the algorithm? Include the
number of iterations it would take? Draw an X if the person can’t be found.
i 0 1 2 3 4 5 6 7
name Carnival Scooby Daphne Shaggy Scrappy Mystery Vincent Velma
Creeper Doo Doo Machine Van
Ghoul
Binary
Search
AP CSA Unit 7 Study Guide -- ArrayList
Sorting
● Selection sort and insertion sort are iterative sorting algorithms that can be used to
sort elements in an array or ArrayList.
● Informal run-time comparisons of program code segments can be made using
comparison statement counts.
12.In the tables below show what state the list will be in after each pass of Selection Sort
and Insertion Sort. A single “pass” means 1 iteration of the outside for loop. Both
algorithms will take n - 1 passes.
Selection Sort
68 33 13 1 55 74 32 70
Insertion Sort
68 33 13 1 55 74 32 70
AP CSA Unit 7 Study Guide -- ArrayList
13.Compare the runtimes of the insertion sort and selection sort algorithms by
counting how many comparisons each requires with the given data.
Simon Obaid Michael JT Andy Adrian
Selection
Insertion
14.Compare the runtimes of the insertion sort and selection sort algorithms by
counting how many comparisons each requires with the given data.
Alex Adrian Andy JT Simon Obaid
Selection
Insertion
15.Rank the algorithms from fastest to slowest based on its Worst Case scenario
Complexity.
Insertion Sort _______
[Link]() _______
Linear Search _______
Binary Search _______
A method that always returns the first element of an array ______
16.Determine whether or not the statement applies to Insertion or Selection sort.
Is the faster of the two if the data is nearly sorted ______
Typically results in less memory writing _______
Will still work if data is added to the list during the sorting process _______
Written with two for loops ______
The runtime of the algorithm is independent of starting order ______