4.10 Implementing ArrayList Algorithms

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:

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?

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.

Check your understanding: What will print when the following code executes?

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.

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 ArrayLists 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
• ArrayList Toggle Code Practice
• ArrayList Coding Practice
• ArrayList Multiple-Choice Exercises

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
• Climb Club A FRQ
• Climb Club B FRQ
• Climb Club C FRQ
• Cookie Order A FRQ
• Cookie Order B FRQ
• StringFormatter Q4 A FRQ
• StringFormatter Q4 B FRQ
• Delimiters Q3 A FRQ
• Delimiters Q3 B FRQ