# 4.10 Implementing ArrayList Algorithms

Each coding exercise has its own folder. Open its `.java` file and press **Run** to try it. **Run Tests** checks every graded exercise in this lesson at once.

There are standard `ArrayList` algorithms that utilize traversals to:

> - insert elements
> - delete elements
> - determine a minimum or maximum value
> - compute a sum or average
> - determine if at least one element has a particular property
> - determine if all elements have a particular property
> - determine the number of elements having a particular property
> - access all consecutive pairs of elements
> - determine the presence or absence of duplicate elements
> - shift or rotate elements left or right
> - reverse the order of the elements

Here are two common `ArrayList` traversal loops that can be used for these algorithms:

```java
for (Type obj : list)
{
    if (obj ....)
        ...
}

for(int i=0; i < list.size(); i++)
{
   if (list.get(i) ....)
       ...
}
```

## Add/Remove Elements

You should be able to trace through code that uses all the basic ArrayList methods like the following.

> Check your understanding: What will print when the following code executes?
>
> ```java
> List<Integer> numList = new ArrayList<Integer>();
> numList.add(new Integer(1));
> numList.add(new Integer(2));
> numList.add(new Integer(3));
> numList.set(2,new Integer(4));
> numList.add(1, new Integer(5));
> numList.add(new Integer(6));
> System.out.println(numList);
> ```
>
> Answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#qListRem3

You can step through the code above by clicking on the following [Example1](https://cscircles.cemc.uwaterloo.ca/java_visualize/#code=import+java.util.*%3B%0A%0Apublic+class+ClassNameHere+%7B%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++%0A++++++List%3CInteger%3E+list1+%3D+new+ArrayList%3CInteger%3E()%3B%0A++++++list1.add(new+Integer(1))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.add(new+Integer(2))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.add(new+Integer(3))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.set(2,+new+Integer(4))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.add(1,+new+Integer(5))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.add(new+Integer(6))%3B%0A++++++System.out.println(list1)%3B%0A++++++%0A+++%7D%0A%7D&mode=display&curInstr=0).

> Check your understanding: What will print when the following code executes?
>
> ```java
> List<Integer> list1 = new ArrayList<Integer>();
> list1.add(new Integer(1));
> list1.add(new Integer(2));
> list1.add(new Integer(3));
> list1.remove(1);
> System.out.println(list1);
> ```
>
> Answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#qListRem4

You can step through the code above by clicking on the following [Example2](https://cscircles.cemc.uwaterloo.ca/java_visualize/#code=import+java.util.*%3B%0A%0Apublic+class+ClassNameHere+%7B%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++List%3CInteger%3E+list1+%3D+new+ArrayList%3CInteger%3E()%3B%0A++++++list1.add(new+Integer(1))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.add(new+Integer(2))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.add(new+Integer(3))%3B%0A++++++System.out.println(list1)%3B%0A++++++list1.remove(1)%3B%0A++++++System.out.println(list1)%3B%0A+++%7D%0A%7D&mode=display&curInstr=0).

### Exercise 1

The code is supposed to initialize the ArrayList arr to [0,1,2,3,4] and then remove every other element to get [1,3]. However, when you remove an element the size of the array changes and elements move up an index! See if you can figure out why you get the unexpected result.

> Open the `01-arrayListRemoveInLoop` folder and run `ArrayListLoop.java`. It is an example, so it has no tests.

> If you use add or remove inside a loop that traverses an `ArrayList`, you may get unexpected results because the size of the `ArrayList` has changed! Enhanced `for` should not be used to remove elements from an `ArrayList`.

## Min, Max, Sum, Average

You should be able to write code that finds the minimum, maximum, sum, and average of the elements in an `ArrayList`.

> Check your understanding: The following method should calculate the average from an ArrayList of Integers (the parameter). But, the blocks have been mixed up and include one extra block that is not needed in a correct solution. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#arraylistAvgParsons

> Check your understanding: The following program segment is a method that should return the minimum int given an ArrayList of Integers (the parameter). But, the blocks have been mixed up and include one extra block that is not needed in a correct solution. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#arraylistMinParsons

### Exercise 2

Create a `findMax` method that finds and returns the largest value in an ArrayList of Integers.

> Open the `02-arraylistMax` folder and edit `ListMax.java`. Press **Run** to try it; **Run Tests** checks it (2 tests).

## Finding a property

You should be able to write code that determines if at least one element has a particular property, if all elements have a particular property, or the number of elements having a particular property. This means that you will need to use an `if` statement to check for the property inside a loop. In the AP exam, the property is often given as boolean method for you to use inside the loop, for example `isEven(num)` returns true if the number is even.

> Check your understanding: The following program segment is a method that should return true if at least one element in an ArrayList of Integers (the parameter) is even. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#arraylistEvenParsons

The following method counts the number of odd numbers in an `ArrayList` of Integers.

### Exercise 3

Write a method `countOdd` that returns the number of odd numbers in an ArrayList of Integers.

> Open the `03-countOddArrayList` folder and edit `TestCountOdd.java`. Press **Run** to try it; **Run Tests** checks it (2 tests).

## Pairs and Duplicates

In the last lesson, the coding challenge involved finding pairs. You should be able to write code that accesses all consecutive pairs of elements in an `ArrayList` and determines the presence or absence of duplicate elements. These problems often require nested loops.

> Check your understanding: The following program segment is a method that should return true if there are any duplicate elements in an ArrayList of Integers (the parameter). — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#arraylistDuplicatesParsons

### Exercise 4

Write a method `hasDuplicates` that returns true if there are any duplicate elements in an ArrayList of Integers.

> Open the `04-arraylistDuplicates` folder and edit `TestDuplicates.java`. Press **Run** to try it; **Run Tests** checks it (4 tests).

## Shift/Rotate an `ArrayList`

We can write code that shifts or rotates elements left or right in an `ArrayList`. The following code rotates the elements in an `ArrayList` to the right by one position.

> Check your understanding: The following program segment is a method that should rotate the elements in an ArrayList of Integers (the parameter) to the right by one position. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#rotateArrayListParsons

### Exercise 5

Write a method `rotateLeft` that rotates the elements in an `ArrayList` of Integers to the left by one position.

> Open the `05-rotateNewList` folder and edit `TestRotate.java`. Press **Run** to try it; **Run Tests** checks it (2 tests).

## Reversing an `ArrayList`

The following examples reverse the order of the elements in an `ArrayList` by adding each element to the beginning of a new `String` or `ArrayList`.

> Check your understanding: The following program segment should be a method that traverses through an ArrayList of Strings (the parameter) and print out the elements in reverse order – so {“cat”, “dog”, “mouse”} should print “mouse, dog, cat, ” as output. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-10-arraylist-algorithms.html#reverseArrayListParsons

### Exercise 6

Complete the method `reverse` to return an `ArrayList` containing Integers in the reversed order of the ArrayList parameter `list`. Hint: use a for loop with one line inside it to add to the new list.

> Open the `06-reverseNewList` folder and edit `TestReverse.java`. Press **Run** to try it; **Run Tests** checks it (3 tests).

## Multiple or Parallel Data Structures

Some algorithms require multiple `String`, array, or `ArrayList` objects to be traversed simultaneously. For example, the following code traverses two parallel `ArrayList`s that hold the grades for different tests.

### Exercise 7

Complete the code to add the items in parallel ArrayLists to total.

> Open the `07-parallelArrayLists` folder and edit `ParallelTests.java`. Press **Run** to try it; **Run Tests** checks it (2 tests).

## Summary

- (AP 4.10.A.1) There are standard `ArrayList` algorithms that utilize traversals to:
  > - determine a minimum or maximum value
  > - compute a sum or average
  > - determine if at least one element has a particular property
  > - determine if all elements have a particular property
  > - determine the number of elements having a particular property
  > - access all consecutive pairs of elements
  > - determine the presence or absence of duplicate elements
  > - shift or rotate elements left or right
  > - reverse the order of the elements
  > - insert elements
  > - delete elements
- (AP 4.10.A.2) Some algorithms require multiple String, array, or ArrayList objects to be traversed simultaneously.

## Review and FRQ Practice with ArrayLists

This lesson ends the `ArrayList` section of this unit. You can now do the following review lessons and FRQs at the end of the unit.

- [ArrayList Summary](https://runestone.academy/ns/books/published/csawesome2/ArrayList-summary.html)
- [ArrayList Toggle Code Practice](/lessons/CSA-4-Toggle-Code-Practice-4b-ArrayList)
- [ArrayList Coding Practice](/lessons/CSA-4-Code-Practice-with-ArrayLists)
- [ArrayList Multiple-Choice Exercises](https://runestone.academy/ns/books/published/csawesome2/ArrayList-Exercises.html)

We encourage you to work in pairs or groups to tackle the following challenging FRQ problems and take them one step at a time. These will get easier with practice!

- [FRQ 3 ArrayList Inventory](/lessons/CSA-4-Free-Response-Question-FRQ-3-ItemInventory)
- [Climb Club A FRQ](/lessons/CSA-4-Free-Response-Climbing-Club-A)
- [Climb Club B FRQ](/lessons/CSA-4-Free-Response-Climbing-Club-B)
- [Climb Club C FRQ](/lessons/CSA-4-Free-Response-Climbing-Club-C)
- [Cookie Order A FRQ](/lessons/CSA-4-Free-Response-CookieOrder-A)
- [Cookie Order B FRQ](/lessons/CSA-4-Free-Response-CookieOrder-B)
- [StringFormatter Q4 A FRQ](/lessons/CSA-4-Free-Response-StringFormatter-A)
- [StringFormatter Q4 B FRQ](/lessons/CSA-4-Free-Response-StringFormatter-B)
- [Delimiters Q3 A FRQ](/lessons/CSA-4-Free-Response-Delimiters-A)
- [Delimiters Q3 B FRQ](/lessons/CSA-4-Free-Response-Delimiters-B)